Why can't we just use preorder traversal to check if a tree is subtree of binary tree? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T05:53:48Z https://cs.stackexchange.com/feeds/question/96497 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/96497 1 Why can't we just use preorder traversal to check if a tree is subtree of binary tree? Ryan Cyrus https://cs.stackexchange.com/users/88691 2018-08-22T05:31:10Z 2018-10-21T19:00:27Z <p>Is preorder traversal enough to check if a tree is subtree of a binary tree?</p> <p>Are there any scenarios which I can miss if I use just the preorder traversal?</p> <p>What other methods can be used to check if a tree is subtree?</p> <p>Also, what happens if my binary tree contains non-unique values at nodes?</p> https://cs.stackexchange.com/questions/96497/-/96499#96499 2 Answer by Raphael for Why can't we just use preorder traversal to check if a tree is subtree of binary tree? Raphael https://cs.stackexchange.com/users/98 2018-08-22T05:38:24Z 2018-08-22T05:38:24Z <p>Because different trees can have the same pre-order label sequence (easy exercise).</p> <p>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.</p> https://cs.stackexchange.com/questions/96497/-/96528#96528 0 Answer by Bulat for Why can't we just use preorder traversal to check if a tree is subtree of binary tree? Bulat https://cs.stackexchange.com/users/8825 2018-08-22T17:07:10Z 2018-08-22T17:07:10Z <p>You can use the following algo to check whether tree SMALL is a part of tree LARGE:</p> <ol> <li>Compute height of smaller tree: small_height = height(SMALL)</li> <li>Recurse large tree, computing height in each node</li> <li>If node height is the same as small tree height, compare trees:</li> </ol> <p><code> 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 </code></p> <p>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).</p>