Identical binary trees

"Given two binary trees, check if they are identical." This is one of the cleanest recursion problems you will encounter, and it shows up frequently at Amazon, Facebook, and Oracle. Also known as Same Tree on LeetCode, this problem distills tree recursion into its purest form: compare, recurse left, recurse right. If you can write this solution confidently, you understand the recursive pattern that powers nearly every binary tree problem.

TL;DR

Check three conditions in order: (1) if exactly one tree is null, return false, (2) if both are null, return true, (3) compare the current node values and recursively check both subtrees. Three lines of logic, O(n) time, O(n) space.

Why This Problem Matters

Identical binary trees is a foundational tree recursion problem. The pattern here, comparing corresponding nodes and recursing into subtrees, appears everywhere: checking subtrees, validating BSTs, comparing symmetric trees, serializing and deserializing trees. Master this, and you have a template for an entire family of tree problems.

Understanding the Problem

Given the root nodes of two binary trees, return true if the trees are identical and false otherwise. Two trees are identical when they have the same shape and the same data at every node.

Here are two identical trees with the representation 1 2 3 # # 4 5:

Both trees have the exact same structure and values. areIdentical(treeA, treeB) returns true.

Now consider two trees that look similar but differ:

Tree A has root 1 with left child 2. Tree B has root 2 with left child 1. Different root values means areIdentical(treeA, treeB) returns false immediately.

Structure matters too, not just values:

Both trees contain nodes 1 and 2, but the child is on the left in one tree and on the right in the other. Same values, different structure, not identical.

Examples

areIdentical(1 2 3 # # 4 5, 1 2 3 # # 4 5) -> true
areIdentical(1 2 3, 1 2 3) -> true
areIdentical(1 2, 2 1) -> false

Solution Approach

The recursive approach mirrors how you would compare two trees by hand: look at the current nodes, then check the left subtrees, then check the right subtrees.

Step 1: Handle the null cases. If exactly one node is null and the other is not, the trees differ structurally. If both are null, we have reached the end of both branches simultaneously, which means they match.

Step 2: Compare values. If both nodes exist, check whether their data is equal.

Step 3: Recurse. Recursively compare the left subtrees and the right subtrees. Both must return true for the trees to be identical.

The XOR Trick for Null Detection

Before comparing values, we need to handle the case where one node is null and the other is not. The XOR operator provides an elegant single-expression check:

• null XOR null = false (both null, keep going)
• null XOR node = true (mismatch detected)
• node XOR null = true (mismatch detected)
• node XOR node = false (both exist, compare values)

Here is the recursive trace for two identical trees 1 2 3 # # 4 5:

Every pair of corresponding nodes matches, so the result bubbles up as true.

Now watch what happens when the trees differ. Comparing 1 2 3 against 1 # 2 (left child exists in one tree but not the other):

The XOR check catches the mismatch immediately. Node 2 exists in one tree, but the corresponding position is null in the other. No need to traverse the rest of the tree.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public Boolean areIdentical(TreeNode t1, TreeNode t2) {
    // If exactly one tree is null, they differ structurally
    if (t1 == null ^ t2 == null) {
      return false;
    }

    // If both are null, both branches ended at the same depth
    else if (t1 == null) {
      return true;
    }

    // Compare current values and recurse into both subtrees
    else {
      return t1.data == t2.data &&
             areIdentical(t1.left, t2.left) &&
             areIdentical(t1.right, t2.right);
    }
  }
}

Walking through the logic:

1. XOR null check: t1 == null ^ t2 == null is true only when exactly one of the two is null. This catches structural mismatches in a single expression.
2. Both null: If both are null (and we already ruled out only-one-null), the branches match. Return true.
3. Recursive comparison: Compare the data at the current nodes, then recurse into left and right subtrees. Short-circuit evaluation means if the data does not match, the subtree calls never execute.

Complexity Analysis

Time: O(n), where n is the number of nodes in the smaller tree. In the best case, the algorithm returns false at the root (O(1)). In the worst case, both trees are identical and every node is visited once.

Space: O(n) for the recursion call stack. The worst case occurs when the tree is completely skewed (every node has only one child), making the recursion depth equal to n. For a balanced tree, the depth is O(log n).

Common Pitfalls

1. Forgetting the XOR check. If you only check t1 == null && t2 == null, you miss the case where one is null and the other is not. This leads to a NullPointerException when you try to access .data on a null node.

2. Checking data before null. Always handle the null cases first. Accessing .data on a null reference crashes the program. The null checks act as guards for the value comparison.

3. Returning early on matching data without recursing. Matching root values does not mean the trees are identical. You must check every node, not just the roots. The recursive calls handle this.

4. Confusing structural equality with value equality. Trees 1 2 (left child) and 1 # 2 (right child) have the same set of values but different structures. They are not identical.

Interview Tips

When presenting this solution:

• State the three cases upfront: one null, both null, both exist. This shows structured thinking.
• Mention short-circuit evaluation. The && operator means if values differ, we skip the subtree comparisons. Interviewers appreciate awareness of performance details.
• Draw two small trees and trace the recursion. Visual examples make your explanation concrete.
• Offer the iterative alternative proactively. Mention that a queue-based BFS approach works too, and you would use it for extremely deep trees to avoid stack overflow.
• Discuss the XOR trick. It is a clean, idiomatic way to check "exactly one of two conditions is true." This signals familiarity with bitwise operations.

Key Takeaways

• Identical binary trees requires checking both structure and values. Two trees with the same values but different shapes are not identical.
• The recursive solution has three cases: one null (false), both null (true), both exist (compare and recurse). This three-case pattern applies to many tree comparison problems.
• Time complexity is O(n) because each node is visited at most once. Space is O(n) in the worst case due to recursion depth on skewed trees.
• Short-circuit evaluation with && ensures the algorithm stops early when a mismatch is found, avoiding unnecessary traversal.
• The XOR null check is an elegant way to detect when exactly one of two references is null.

Practice and Related Problems

Once you have nailed identical binary trees, try these natural progressions:

• Symmetric tree (check if a tree is a mirror of itself)
• Subtree of another tree (uses identical tree check as a subroutine)
• Height of a binary tree (another fundamental tree recursion problem)

This problem and hundreds of others are available on Firecode, where spaced repetition ensures you internalize patterns like tree recursion rather than just memorizing solutions. Building strong recursive thinking here pays dividends across your entire interview preparation.

Solutions in Other Languages

Python

class Solution:
    def are_identical(self, t1: TreeNode, t2: TreeNode) -> bool:
        if (t1 is None) ^ (t2 is None):
            return False

        elif t1 is None:
            return True

        else:
            return (t1.data == t2.data) and \
                   self.are_identical(t1.left, t2.left) and \
                   self.are_identical(t1.right, t2.right)

JavaScript

class Solution {
  areIdentical(t1, t2) {
    if (t1 === null ^ t2 === null) {
      return false;
    }

    else if (t1 === null) {
      return true;
    }

    else {
      return t1.data === t2.data &&
             this.areIdentical(t1.left, t2.left) &&
             this.areIdentical(t1.right, t2.right);
    }
  }
}

TypeScript

class Solution {
  areIdentical(t1: TreeNode | null, t2: TreeNode | null): boolean {
    if ((t1 === null) !== (t2 === null)) {
      return false;
    }

    else if (t1 === null) {
      return true;
    }

    else {
      return t1.data === t2.data &&
             this.areIdentical(t1.left, t2.left) &&
             this.areIdentical(t1.right, t2.right);
    }
  }
}

C++

class Solution {
public:
  bool areIdentical(TreeNode *t1, TreeNode *t2) {
    if (t1 == nullptr ^ t2 == nullptr) {
      return false;
    }

    else if (t1 == nullptr) {
      return true;
    }

    else {
      return t1->data == t2->data &&
             areIdentical(t1->left, t2->left) &&
             areIdentical(t1->right, t2->right);
    }
  }
};

Go

package solution

func (s *Solution) AreIdentical(t1 *TreeNode, t2 *TreeNode) bool {
    if (t1 == nil) != (t2 == nil) {
        return false
    } else if t1 == nil {
        return true
    } else {
        return t1.Data == t2.Data &&
            s.AreIdentical(t1.Left, t2.Left) &&
            s.AreIdentical(t1.Right, t2.Right)
    }
}

Scala

class Solution {
  def areIdentical(t1: TreeNode, t2: TreeNode): Boolean = {
    if (t1 == null ^ t2 == null) {
      false
    }

    else if (t1 == null) {
      true
    }

    else {
      t1.data == t2.data &&
        areIdentical(t1.left, t2.left) &&
        areIdentical(t1.right, t2.right)
    }
  }
}

Kotlin

class Solution {
    fun areIdentical(t1: TreeNode?, t2: TreeNode?): Boolean {
        if ((t1 == null) xor (t2 == null)) {
            return false
        }

        else if (t1 == null) {
            return true
        }

        else {
            return t1!!.data == t2!!.data &&
                   areIdentical(t1.left, t2.left) &&
                   areIdentical(t1.right, t2.right)
        }
    }
}

Swift

class Solution {
    func areIdentical(_ t1: TreeNode?, _ t2: TreeNode?) -> Bool {
        if (t1 == nil) != (t2 == nil) {
            return false
        }

        if t1 == nil {
            return true
        }

        return t1!.data == t2!.data &&
               areIdentical(t1!.left, t2!.left) &&
               areIdentical(t1!.right, t2!.right)
    }
}

Rust

impl Solution {
    pub fn are_identical(&self, t1: Option<Box<TreeNode>>, t2: Option<Box<TreeNode>>) -> bool {
        if t1.is_none() != t2.is_none() {
            return false;
        }

        if t1.is_none() {
            return true;
        }

        let n1 = t1.unwrap();
        let n2 = t2.unwrap();
        n1.data == n2.data
            && self.are_identical(n1.left, n2.left)
            && self.are_identical(n1.right, n2.right)
    }
}

C#

public class Solution {
    public bool AreIdentical(TreeNode? t1, TreeNode? t2) {
        if (t1 == null ^ t2 == null) {
            return false;
        }

        else if (t1 == null) {
            return true;
        }

        else {
            return t1.data == t2.data &&
                   AreIdentical(t1.left, t2.left) &&
                   AreIdentical(t1.right, t2.right);
        }
    }
}

Dart

class Solution {
  bool areIdentical(TreeNode? t1, TreeNode? t2) {
    if ((t1 == null) ^ (t2 == null)) {
      return false;
    }

    else if (t1 == null) {
      return true;
    }

    else {
      return t1!.data == t2!.data &&
             areIdentical(t1.left, t2.left) &&
             areIdentical(t1.right, t2.right);
    }
  }
}

PHP

class Solution {
    public function areIdentical(?TreeNode $t1, ?TreeNode $t2): bool {
        if ($t1 === null xor $t2 === null) {
            return false;
        }

        elseif ($t1 === null) {
            return true;
        }

        else {
            return $t1->data === $t2->data &&
                   $this->areIdentical($t1->left, $t2->left) &&
                   $this->areIdentical($t1->right, $t2->right);
        }
    }
}

Ruby

class Solution
  def are_identical(t1, t2)
    if t1.nil? ^ t2.nil?
      false
    elsif t1.nil?
      true
    else
      t1.data == t2.data &&
        are_identical(t1.left, t2.left) &&
        are_identical(t1.right, t2.right)
    end
  end
end