Check if a tree is the subtree of another binary tree

The straight forward way is to check recursively for every node in the binary tree

Given two binary trees, check if the first tree is subtree of the second one. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T.

The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.

For example, in the following case, Tree1 is a subtree of Tree2.

Tree1
x
/ \
a b
\
c

Tree2
z
/ \
x e
/ \ \
a b k
\
c

The straight forward solution is to traverse the Tree2. We check if the Tree1 is the same as the tree rooted with the traversed node. This will result in a O(m*n) run time.

The other way to attack this problem is to use the tree traversal. A binary tree can be reconstructed using the post-order + in-order or pre-order + in-order traversal. So we can simply get the pre-order and in-order traversal of both tree. and check if the traversal of tree1 is the corresponding traversal of tree2. The traversal has running time of O(n) and checking substring by using the kmp algorithm is O(n) time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s