How to check if a Tree is subtree of another Tree?

ALSO CHECK: Algorithms and System Design Interview Questions

To check if the given tree is subtree of another tree, first we need to undertand if the how can we check if the tree's are identical or not.

Please visit: Check if two Binary Trees are Identical or not?

To verify if a tree is subtree of another, we need to traverse the Tree T in a preorder fashion.For every visited node in the traversal, see if the subtree rooted with this node is identical to another tree S.


Here is the Algorithm to check if a Tree is subtree of another Tree:

boolean isSubTree(Node T, Node S){
  if(S==null)
    return true;
  if(T==null)
    return false;
  if(isIdentical(T, S))
    return true;
  
  return (isSubTree(T.left, S) ||
          isSubTree(T.right, S));
}

GIT URL: Check if a Tree is subtree of another Tree
Java Solution

Time Complexity
Time worst case complexity of above solution is O(xy), where x and y are number of nodes in given two trees.

-K Himaanshu Shuklaa..