Find if a Tree is Subtree of another Tree

Introduction

This is a simple yet non trivial problem. Given two trees we need to evaluate if one tree is the sub tree of the other. If the condition is satisfied, it returns true, else it returns false.

The definition of sub tree must not be ambiguous. We say that two trees are equal if they are structurally equal and their corresponding nodes have equal keys.

Equality of trees

Remember that subtree and contains relation are not the same. It may be possible that a tree T1 contains another tree T2 and still T2 is not a sub tree of T1.

This also means that all subtree satisfies the contains relation but not all contains relation satisfies the subtree relation.

Subtree Relation

gif2
In the above animation, the green tree is a subtree of the grey tree.

Contains Relation

gif1
In the above animation, the red tree is contained in the grey tree.

Why is the red tree not a sub tree?
It is fairly simple to see that if we lift the red tree and place it on the grey tree to align its nodes with the corresponding nodes of the grey tree, the node with value 7 is still left over as shown in the second animation above.

Where as if we lift the green tree and place it on the grey tree to align its nodes with the corresponding nodes of the grey tree. It perfectly covers the section and nothing spills over.

Equality relation

Two trees are equal if placing one tree over the other covers up the complete tree. Which simplifies our definition to the following:

Two trees T1 and T2 are said to be equal if,

  • The root of T1 is equal to the root of T2.
  • The subtrees for each of T1’s children is equal to the corresponding subtrees for each of T2’s children.

Idea behind the solution

The definition of equality itself is recursive. Hence it would be easy if we think in a recursive manner. So, let us say we have some mechanism of comparing two trees given their root, and it returns a true or a false depending on the success or failure of the comparison respectively.

Algorithm to find the existence of a subtree

The algorithm now reduces to the following:

  • Start from the root of T1 and T2
  • Invoke the comparison method passing both the roots.
  • If the comparison evaluates the tree to be equal, return true.
  • If the above comparison returned false, compare T1’s root with T2’s each child individually and return the OR of the results

As the whole process is recursive, hence it will end up after evaluating all the possibilities.

The question now is to develop a comparison algorithm, here it is.

Algorithm to compare two trees
  • Compare the two roots. If they are unequal, return false
  • If they are equal compare each child of T1 with the corresponding child of T2 recursively
  • return true

Source Code to Find if a Tree is Subtree of another Tree

You can download the complete source code from the Github Link for TechieMe.

Here is the important methods:

code for subtree test

Code for Comparing Trees

Analysis

The comparison algorithm takes O(N) time, where N is the number of nodes in the smaller tree. However, for simplicity, let us consider that both the trees have same number of nodes and that is N.

The subtree algorithm needs to evaluate each node of tree T2 , for the root of T1. For each evaluation it invokes the comparison routine. SO ideally it is a O(N2) solution in the worst case.

Conclusion

This problem can also be extended to test if a tree is contained into another tree. This is an excessive use of recursion, a non-recursive code is also possible, which might need some extra space.

Also, this piece of solution contains a solution for another problem which is to test equality of two trees.

Advice : Please do not get tempted to find sub array sequences for in order, pre order and post order strings. It doesn’t work in many test cases.

Don’t forget to subscribe to TechieMe to get updates on latest posts.