Check If Two Binary Trees Are Equal - Binary Tree

We can check if two binary trees are equal by simply verifying that the root nodes have the same value, and that the left subtrees are equal, and the right subtrees are equal. Here's a possible implementation:

bool areEqual(Node *root1, Node *root2) {
  if (root1 == nullptr && root2 == nullptr) return true;
  if (root1 == nullptr || root2 == nullptr) return false;
  if (root1->value != root2->value) return false;

  return areEqual(root1->left, root2->left) &&
         areEqual(root1->right, root2->right);
}

Time complexity

The time complexity is O(min(n1, n2)) (where n1 is the size of the first tree, and n2 is the size of the second tree) because that's the total work done when we combine the work done by each recursive call. See the video for more detail.

Space complexity

The space complexity is O(min(h1, h2)) (where h1 is the height of the first tree, and h2 is the height of the second tree) because of the space taken by the call stack. See the video for more detail.

Video with explanation