isSubtree Problem

isSubtree Problem

Problem Statement:

Given two binary trees t1 and t2, determine whether the second tree is a subtree of the first tree.

As t2 is a part of t1, hence output will be true

Output for the above example is true.

boolean isSubTree(Tree<Integer> t1, Tree<Integer> t2) {
    if (t2 == null)  // Empty tree will always be subtree of any t1
        return true;

    if (t1 == null) // If t1 is null but t2 is not, then return false
        return false;

    if (isEqual(t1, t2))  // Check if both t1 or t2 are same or not
        return true;
    // Keep checking with t1's left and right node to t2
    return isSubTree(t1.left, t2) || isSubTree(t1.right, t2);
}

// The below method checks if given two trees are identical or not
boolean isEqual(Tree<Integer> root1, Tree<Integer> root2) {
    if (root1 == null && root2 == null)
        return true;
    if (root1 == null || root2 == null)
        return false;
    return (root1.value.equals(root2.value)
            && isEqual(root1.left, root2.left)
            && isEqual(root1.right, root2.right));
}

Time Complexity: O(m*n) - where m and n are the respective numbers of nodes in t1 and t2