Check if Two Binary Trees are Identical

editor-page-cover

Problem Statement

Given the roots of two binary trees, determine if these trees are identical or not. Identical trees have the same layout and data at each node. Consider the following two identical binary trees that have the same layout and data.

widget

It is not necessary that trees that have the same data are identical trees. Trees that have the exact same data may not be structurally identical. For example if you look at the two trees below, although they have the same data, they are not identical.

widget

Hint

  • Depth first traversal
  • Recursion

Try it yourself

bool are_identical(
  BinaryTreeNode* root1,
  BinaryTreeNode* root2) {
  //TODO: Write - Your - Code
  return false;
}

Solution

bool are_identical(
  BinaryTreeNode* root1,
  BinaryTreeNode* root2) {

  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  
  if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            are_identical(root1->left, root2->left) &&
            are_identical(root1->right, root2->right));
  }

  return false;
}

int main() {
  BinaryTreeNode *root1 = new BinaryTreeNode(100);
  insert_bst(root1, 50);
  insert_bst(root1, 200);
  insert_bst(root1, 25);
  insert_bst(root1, 125);
  insert_bst(root1, 350);

  display_level_order(root1);
  
  BinaryTreeNode *root2 = create_random_BST(15);

  display_level_order(root2);
  
  // Try changing the roots being passed
  if(are_identical(root1, root2)) {
    cout<< " the trees are identical" << endl;
  } else {
    cout<< "the trees are not identical" << endl;
  }
}

Solution Explanation

Runtime Complexity

Linear, O(n).

Memory Complexity

O(h)

The recursive solution has O(h) memory complexity as it will consume memory on the stack up to the height of binary tree h. It will be O(log n) for a balanced tree and in the worst case can be O(n).


Solution Breakdown

This problem can be effectively solved using a recursive solution. The base case of recursion for this solution is if both nodes being compared are null, or one of them is null.

Two trees ‘A’ and ‘B’ are identical if:

  • data on their roots is the same or both roots are null
  • left sub-tree of ‘A’ is identical to the left sub-tree of ‘B’
  • right sub-tree of ‘A’ is identical to the right sub-tree of ‘B’

To solve this problem, we’ll do a depth-first traversal on both trees simultaneously and keep comparing the data at each level.