July 28, 2019

How to check of two Binary Trees are Identical?

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..

No comments:

Post a Comment