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
private boolean findSubtree(BNode T1, BNode T2) {
    // T1 is assumed to be the larger tree. If T1 is null and T2 is not null then there cannot be any subtree possible
    if (T1 == null && T2 != null)
        return false;
    // null is always a valid subtree of any tree.
    if(T2 == null)
        return true;
		
    boolean comparisonResult = compareTrees(T1, T2);
    if (comparisonResult)
        return true;

    return (findSubtree(T1.right, T2) || findSubtree( T1.left, T2));
}
Code for Comparing Trees
private boolean compareTrees(BNode T1, BNode T2) {
    if (T1 == null && T2 == null)
        return true;

    if (T1 == null || T2 == null)
        return false;

    if (T1.data == T2.data)
        return compareTrees(T1.left, T2.left) && compareTrees(T1.right, T2.right);
    
    return false;
}

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.