Same Tree

You are given the roots p and q of two binary trees. Decide whether they are identical: the two trees must have exactly the same shape, and every pair of nodes in matching positions must hold equal values.

Return true if they are identical and false otherwise. Two empty trees count as identical.

Trees are given in level order with null marking a missing child. Note that a left child and a right child are different positions, so [4,5] (5 on the left) and [4,null,5] (5 on the right) are not the same tree.

Example 1

Example 2

Example 3

Constraints

• Each tree has between 0 and 2000 nodes.
• The depth of each tree is at most 500.
• -104 <= Node.val <= 104

Pattern Path · Trees: DFS · problem 84 of 169

Start simple

Serialising both trees (including null markers) and comparing the strings also works in O(n) time but builds O(n) extra data; comparing in place is simpler.

The key idea

Equality of trees has a natural recursive definition. Two trees are the same if and only if:

• both are empty, or
• both are non-empty, their roots have equal values, their left subtrees are the same, and their right subtrees are the same.

So compare the two current nodes. If both are null, this part matches. If exactly one is null, the shapes differ. If the values differ, the trees differ. Otherwise recurse into the left pair and the right pair, and require both to match.

Because and short-circuits, the search stops at the first mismatch. In the worst case (identical trees) every node is compared once. The null checks are what make the comparison sensitive to shape, not just to the set of values, which is why [4,5] and [4,null,5] are correctly reported as different.

Complexity

• Time: O(min(n, m))
• Space: O(h) for the recursion, where h is the smaller height

Python

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

JavaScript

var isSameTree = function(p, q) {
  if (p === null && q === null) return true;
  if (p === null || q === null || p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

What the interviewer is checking

A clean test of recursive thinking on two structures at once, especially getting the null base cases in the right order.

Mistakes to avoid

• Reading p.val before checking that both nodes exist.
• Comparing only in-order traversals: different shapes can produce the same sequence.
• Ignoring left versus right, so mirrored trees are wrongly treated as equal.

Follow-ups to expect

• Is the tree symmetric? (Compare left subtree with mirrored right.)
• Is q a subtree of p? (Same-tree check at every node, or hashing.)
• Do it iteratively. (Queue or stack of node pairs.)

In real software

Virtual-DOM diffing, comparing abstract syntax trees in compilers and checking structural equality of nested configuration objects all perform this simultaneous walk over two trees.

Practice next