1
$\begingroup$

Is preorder traversal enough to check if a tree is subtree of a binary tree?

Are there any scenarios which I can miss if I use just the preorder traversal?

What other methods can be used to check if a tree is subtree?

Also, what happens if my binary tree contains non-unique values at nodes?

$\endgroup$
1
$\begingroup$

Because different trees can have the same pre-order label sequence (easy exercise).

To check equality, recurse on both trees at the same time. That gives you a simple (if not terribly efficient) algorithm for checking whether a tree is a subtree of another one.

$\endgroup$
  • $\begingroup$ @Raphael I don't understand how can we recurse both tree at the same time? Will we start at the root of both? How will it work? $\endgroup$ – Ryan Cyrus Aug 22 '18 at 16:02
  • $\begingroup$ @RyanCyrus Yes! There are two ways: 1) Don't actually use recursion; as a preparatory exercise, implement pre-order traversal without recursion. 2) Write a recursive function with two parameters; as a preparatory exercise, implement pre-order traversal with recursion. $\endgroup$ – Raphael Aug 22 '18 at 19:42
0
$\begingroup$

You can use the following algo to check whether tree SMALL is a part of tree LARGE:

  1. Compute height of smaller tree: small_height = height(SMALL)
  2. Recurse large tree, computing height in each node
  3. If node height is the same as small tree height, compare trees:

recurse(tree) left_height = recurse(tree.left) right_height = recurse(tree.right) height = max(left_height,right_height) + 1 if height==small_height compare_trees(SMALL,tree) return height

Time analysis is simple: you may visit each node in large tree once or twice - once when computing height and another time when comparing it to small tree. So, browsing large tree is O(n), and computing height of small tree require to visit each node so it's O(m).

$\endgroup$
  • $\begingroup$ The analysis needs a little more work. There can be $\omega(1)$ calls to compare_trees! I think an $O(n)$ bound might still be possible (note that $m \leq n$, so $m \in O(n)$) but you'll need a simple amortization argument. $\endgroup$ – Raphael Aug 22 '18 at 19:45
  • $\begingroup$ Also, I note that this algorithm is essentially the one in my answer, with an early break by height comparison before recursively comparing trees. $\endgroup$ – Raphael Aug 22 '18 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.