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..
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..
No comments:
Post a Comment