Tree Structure Equality Check - How to Compare Two Binary Trees

You're in a phone screen at Adobe when the interviewer asks, "Given two binary trees, write a function to check if they're identical." This problem, also known as Same Tree on other platforms, is one of the most common tree questions in technical interviews. It appears frequently at Meta, Amazon, Apple, and Bloomberg because it tests your ability to think recursively about tree structures. Despite its apparent simplicity, candidates who haven't practiced it often stumble on the null-handling edge cases.

TL;DR

Recursively compare both trees node by node. If both nodes are null, they match. If only one is null, they don't match. If both exist but have different values, they don't match. Otherwise, recursively check the left subtrees and the right subtrees. Return true only if both recursive calls return true. This runs in O(n) time and O(n) space.

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

Why This Problem Matters

The same tree problem is a gateway to recursive tree thinking. The pattern you learn here - "check the current nodes, then recurse on children" - shows up in dozens of other tree problems: symmetric tree, subtree checking, tree serialization, and more. Companies like Adobe (where this problem has an interview frequency of 8) use it as a quick filter to separate candidates who understand recursion from those who don't.

Understanding the Problem

Given the roots of two binary trees, firstTree and secondTree, determine if these trees are identical. Two trees are identical when they have the same structure and every corresponding node holds the same value.

Example 1: Identical Trees

firstTree: [1, 2, 3]

secondTree: [1, 2, 3]

Both trees have the same shape and the same values at each position. isSameTree(firstTree, secondTree) returns true.

Example 2: Different Structure

firstTree: [1, 2, #] - node 2 is the left child

secondTree: [1, #, 2] - node 2 is the right child

The values are the same, but node 2 sits on different sides. Structure matters. isSameTree(firstTree, secondTree) returns false.

Constraints

• The number of nodes in both trees is within the range [0, 100]
• Each node's value is between -10,000 and 10,000 inclusive

Edge Cases

1. Both trees are null: Two empty trees are identical, return true
2. One tree is null: An empty tree and a non-empty tree are never identical, return false
3. Single node trees: Compare the single values directly
4. Same values, different structure: [1, 2, 1] vs [1, 1, 2] are not identical

The Recursive Insight

Trees have a natural recursive structure. Every subtree is itself a valid binary tree. This means you can break the problem down: two trees are identical if and only if their roots have the same value AND their left subtrees are identical AND their right subtrees are identical.

The recursion terminates at null nodes. When both nodes are null, you've reached matching leaf boundaries. When only one is null, you've found a structural difference.

Base case: when both nodes are null, the empty subtrees are identical.

Solution Approach

The algorithm follows three checks at each pair of nodes:

1. Both null? Return true - matching empty subtrees
2. One null? Return false - structural mismatch
3. Values differ? Return false - data mismatch
4. All checks pass? Recurse on left children AND right children

This depth-first traversal visits each node exactly once, comparing it with its counterpart in the other tree.

Implementation

public class Solution {
  public boolean isSameTree(TreeNode firstTree, TreeNode secondTree) {
    if (firstTree == null && secondTree == null) {
      return true;
    }
    if (firstTree == null || secondTree == null) {
      return false;
    }
    if (firstTree.data != secondTree.data) {
      return false;
    }
    return isSameTree(firstTree.left, secondTree.left) && isSameTree(firstTree.right, secondTree.right);
  }
}

Tracing Through Identical Trees

For firstTree = [1, 2, 3] and secondTree = [1, 2, 3]:

The recursion fans out to each subtree, confirms all leaf nodes match at their null boundaries, and propagates true back up to the root.

Tracing Through Different Trees

For firstTree = [1, 2, #] and secondTree = [1, #, 2]:

The left subtree comparison immediately finds a structural mismatch: firstTree.left is node 2 but secondTree.left is null. The function returns false without needing to check the right subtrees.

Walkthrough with a Deeper Tree

For two identical copies of [1, 2, 3, 4, 5]:

The recursion follows every path from root to leaf. Each path is compared with the corresponding path in the second tree. All three paths must match for the trees to be identical.

Complexity Analysis

Time: O(n)

Every node is visited at most once. In the best case, a mismatch at the root returns in O(1). In the worst case, both trees are identical and all n nodes are compared. Each comparison performs O(1) work (null checks and value comparison).

Space: O(n)

The space comes from the recursive call stack. For a balanced tree with n nodes, the maximum recursion depth is O(log n). For a completely skewed tree (every node has only one child), the depth equals n, giving O(n) space in the worst case.

Common Pitfalls

1. Null pointer exceptions: Always check for null before accessing .data, .left, or .right. The order of checks matters - null checks must come before value comparison.

2. Checking values without checking structure: Two trees can have the same values in a different arrangement. [1, 2, 1] and [1, 1, 2] have identical values but different structures.

3. Using OR instead of AND: Both the left subtrees AND the right subtrees must be identical. Using || instead of && would return true if only one subtree matches.

4. Forgetting the single-null case: If firstTree is null and secondTree is not (or vice versa), you must return false. A common mistake is only checking firstTree == null && secondTree == null and skipping the case where exactly one is null.

Interview Tips

1. Start with the base cases: Tell the interviewer, "I'll handle the null cases first, then compare values, then recurse." This shows structured thinking.

2. Draw two small trees side by side: Sketch [1, 2, 3] for both trees and trace through the recursion. Then change one value or move a node to show the failure case.

3. Mention the iterative alternative: "I could also solve this iteratively using a queue with pairs of nodes, but the recursive version is cleaner for this problem." This shows breadth of knowledge.

4. Discuss the complexity clearly: "Time is O(n) because I visit each node once. Space is O(n) worst case for the call stack on a skewed tree, but O(log n) for a balanced tree."

5. Prepare for follow-ups: The interviewer might ask about symmetric tree (mirror comparison), subtree checking (is one tree a subtree of another), or serialization-based comparison.

Key Takeaways

• The recursive formula checks three conditions (both null, one null, values differ) before recursing on both subtrees. Getting the order of these checks right prevents null pointer errors.
• Time complexity is O(n) with early termination on the first mismatch. Space is O(n) worst case for the call stack on skewed trees, O(log n) for balanced trees.
• This "check current node, recurse on children" pattern is the foundation for symmetric tree, subtree of another tree, maximum depth, and many other tree problems.
• Structure equality is as important as value equality. Two trees with identical values arranged differently are not the same tree.
• When both nodes are null simultaneously, that's a successful match at the leaf boundary, not an error condition.

Related Problems

Once you're comfortable with this recursive pattern, try these:

• Height of a Binary Tree - same recursive structure, different computation at each node
• Number of Islands - DFS traversal applied to a grid instead of a tree
• Bracket Harmony Check - recursive structure validation with a stack

These are all available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. The recursive tree pattern you just learned appears in nearly every tree problem you'll encounter.

Solutions in Other Languages

Python

class Solution:
    def is_same_tree(self, first_tree, second_tree):
        if not first_tree and not second_tree:
            return True
        if not first_tree or not second_tree:
            return False
        if first_tree.data != second_tree.data:
            return False
        return self.is_same_tree(first_tree.left, second_tree.left) and self.is_same_tree(first_tree.right, second_tree.right)

JavaScript

class Solution {
  isSameTree(firstTree, secondTree) {
    if (!firstTree && !secondTree) return true;
    if (!firstTree || !secondTree) return false;
    if (firstTree.data !== secondTree.data) return false;
    return this.isSameTree(firstTree.left, secondTree.left) && this.isSameTree(firstTree.right, secondTree.right);
  }
}

TypeScript

class Solution {
    isSameTree(firstTree: TreeNode | null, secondTree: TreeNode | null): boolean {
        if (firstTree === null && secondTree === null) return true;
        if (firstTree === null || secondTree === null) return false;
        if (firstTree.data !== secondTree.data) return false;
        return this.isSameTree(firstTree.left, secondTree.left) && this.isSameTree(firstTree.right, secondTree.right);
    }
}

C++

class Solution {
public:
  bool isSameTree(TreeNode *firstTree, TreeNode *secondTree) {
    if (firstTree == nullptr && secondTree == nullptr) {
      return true;
    }
    if (firstTree == nullptr || secondTree == nullptr) {
      return false;
    }
    if (firstTree->data != secondTree->data) {
      return false;
    }
    return isSameTree(firstTree->left, secondTree->left) && isSameTree(firstTree->right, secondTree->right);
  }
};

Go

func (s *Solution) IsSameTree(firstTree *TreeNode, secondTree *TreeNode) bool {
    if firstTree == nil && secondTree == nil {
        return true
    }
    if firstTree == nil || secondTree == nil {
        return false
    }
    if firstTree.Data != secondTree.Data {
        return false
    }
    return s.IsSameTree(firstTree.Left, secondTree.Left) && s.IsSameTree(firstTree.Right, secondTree.Right)
}

Kotlin

class Solution {
    fun isSameTree(firstTree: TreeNode?, secondTree: TreeNode?): Boolean {
        if (firstTree == null && secondTree == null) {
            return true
        }
        if (firstTree == null || secondTree == null) {
            return false
        }
        if (firstTree.data != secondTree.data) {
            return false
        }
        return isSameTree(firstTree.left, secondTree.left) && isSameTree(firstTree.right, secondTree.right)
    }
}

Scala

class Solution {
  def isSameTree(firstTree: TreeNode, secondTree: TreeNode): Boolean = {
    if (firstTree == null && secondTree == null) {
      true
    } else if (firstTree == null || secondTree == null) {
      false
    } else {
      firstTree.data == secondTree.data && isSameTree(firstTree.left, secondTree.left) && isSameTree(firstTree.right, secondTree.right)
    }
  }
}

Swift

class Solution {
    func isSameTree(_ firstTree: TreeNode?, _ secondTree: TreeNode?) -> Bool {
        if firstTree == nil && secondTree == nil {
            return true
        }
        if firstTree == nil || secondTree == nil {
            return false
        }
        if firstTree!.data != secondTree!.data {
            return false
        }
        return isSameTree(firstTree!.left, secondTree!.left) && isSameTree(firstTree!.right, secondTree!.right)
    }
}

Rust

impl Solution {
    pub fn is_same_tree(&self, first_tree: Option<Box<TreeNode>>, second_tree: Option<Box<TreeNode>>) -> bool {
        if first_tree.is_none() && second_tree.is_none() {
            return true;
        }
        if first_tree.is_none() || second_tree.is_none() {
            return false;
        }
        let first = first_tree.unwrap();
        let second = second_tree.unwrap();
        if first.data != second.data {
            return false;
        }
        self.is_same_tree(first.left, second.left) && self.is_same_tree(first.right, second.right)
    }
}

C#

public class Solution {
    public bool IsSameTree(TreeNode? firstTree, TreeNode? secondTree) {
        if (firstTree == null && secondTree == null) {
            return true;
        }
        if (firstTree == null || secondTree == null) {
            return false;
        }
        if (firstTree.data != secondTree.data) {
            return false;
        }
        return IsSameTree(firstTree.left, secondTree.left) && IsSameTree(firstTree.right, secondTree.right);
    }
}

Dart

class Solution {
  bool isSameTree(TreeNode? firstTree, TreeNode? secondTree) {
    if (firstTree == null && secondTree == null) {
      return true;
    }
    if (firstTree == null || secondTree == null) {
      return false;
    }
    if (firstTree.data != secondTree.data) {
      return false;
    }
    return isSameTree(firstTree.left, secondTree.left) && isSameTree(firstTree.right, secondTree.right);
  }
}

PHP

class Solution {
    public function isSameTree(?TreeNode $firstTree, ?TreeNode $secondTree): bool {
        if ($firstTree === null && $secondTree === null) {
            return true;
        }
        if ($firstTree === null || $secondTree === null) {
            return false;
        }
        if ($firstTree->data !== $secondTree->data) {
            return false;
        }
        return $this->isSameTree($firstTree->left, $secondTree->left) && $this->isSameTree($firstTree->right, $secondTree->right);
    }
}

Ruby

class Solution
  def same_tree?(first_tree, second_tree)
    return true if first_tree.nil? && second_tree.nil?
    return false if first_tree.nil? || second_tree.nil?
    return false if first_tree.data != second_tree.data

    same_tree?(first_tree.left, second_tree.left) && same_tree?(first_tree.right, second_tree.right)
  end
end