# Check two balanced binary search trees that sub set of each other

Given two balanced binary search trees $$T_1,T_2$$. We want to check, are $$T_1\subseteq T_1$$ or not. $$T_1$$ have $$n_1$$ nodes, and $$T_2$$ have $$n_2$$ nodes.

Instructor say it can be done in $$O(n_1+n_2)$$ time complexity with $$O(\log n_1+\log n_2)$$ space.

My idea:

I use in order traverse on two trees , and compare first node in order traverse $$T_1$$ with first node in in order traverse $$T_2$$, and etc. if all nodes in $$T_1$$ present in $$T_2$$ then we say $$T_1\subseteq T_2$$, but i can't prove my space complexity followed from mentioned complexity. Any one can help to guarantee my space complexity be $$O(\log n_1+\log n_2)$$.

• Since the trees are already given, you only need to maintain pointers to two nodes. Depending on the model of computation you are working with those could be responsible for the $O(\log n_1 + \log n_2)$ bound. Mar 16, 2021 at 12:06
• The term pointer wasn't correct I'm sorry. Rather your two balanced binary search trees don't have parent pointers. Meaning that you need to safe the list of parents of your current node (otherwise you would not know the parent of your current node). Since the trees are balanced their depth is $O(\log n)$ at max. Thus the stack in which you store all nodes between your root and the parent of your current node is $\log n$ at max long. Since you do two in-order traversals at the same time you need such a stack for both trees. Mar 16, 2021 at 15:52