0
$\begingroup$

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)$.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – plshelp
    Commented Mar 16, 2021 at 12:06
  • $\begingroup$ Can you more explain about your method? $\endgroup$
    – user132812
    Commented Mar 16, 2021 at 12:32
  • $\begingroup$ 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. $\endgroup$
    – plshelp
    Commented Mar 16, 2021 at 15:52

1 Answer 1

Reset to default
0
$\begingroup$

When you try to traverse a tree, you start at the root, and you will have to remember all the nodes that you were visiting, to be able to find the next node. If your tree is balanced, then it contains only O (log n) nested notes, so your space requirement for two trees is only O(log n) + O(log m). Unbalanced trees could be nested up to n levels deep, so you could need up to O(n) + O(m) space to traverse both trees.

Improve this answer
$\endgroup$