Two Binary trees are identical when they have same data and structure/arrangement of data is also same. To find if they are identical or not, we need to traverse both the trees simultaneously, and in each iteration we will compare the data of current node and the children of both the trees.
ALSO CHECK: Binary Search Trees, Balance Search Trees, 2-3 ST, Red- Black BST
Here is the Algorithm to check if two Binary Trees are identical or not:
boolean isIdentical(Node n1, Node n2){
//two null trees are always identical
if(n1==null && n2==null)
return true;
else if(n1!=null && n2!=null){
if(n1.value==n2.value &&
isIdentical(n1.left, n2.left) &&
isIdentical(n1.right, n2.right))
{
return true;
}
}
return false;
}
GIT URL: Check if two Binary Trees are Identical or not?
Java Solution
Time Complexity
It depend on the tree with lesser number of nodes. Let say the nodes in two trees be x and y then complexity of above approach is is O(x) where x < y.
-K Himaanshu Shuklaa..
ALSO CHECK: Binary Search Trees, Balance Search Trees, 2-3 ST, Red- Black BST
Here is the Algorithm to check if two Binary Trees are identical or not:
boolean isIdentical(Node n1, Node n2){
//two null trees are always identical
if(n1==null && n2==null)
return true;
else if(n1!=null && n2!=null){
if(n1.value==n2.value &&
isIdentical(n1.left, n2.left) &&
isIdentical(n1.right, n2.right))
{
return true;
}
}
return false;
}
GIT URL: Check if two Binary Trees are Identical or not?
Java Solution
Time Complexity
It depend on the tree with lesser number of nodes. Let say the nodes in two trees be x and y then complexity of above approach is is O(x) where x < y.
-K Himaanshu Shuklaa..
No comments:
Post a Comment