Same Tree

EasyTree DFSBlind 75JuniorOpen on LeetCodeUpdated Sep 21, 2026

You're given the roots p and q of two binary trees. Return true if they are the same tree: identical shape, with equal values in every matching position. Return false if a node exists on one side but not the other, or if two matching nodes hold different values. Two empty trees count as the same. Example trees are listed row by row from the top, each row left to right, with null where a child is missing.

Examples

p = [1,2,3], q = [1,2,3] returns true

Both roots are 1 with a left child 2 and a right child 3. Every position matches in shape and value.

p = [1,2], q = [1,null,2] returns false

Both trees hold 1 and 2, but in p the 2 is a left child and in q it is a right child. The shapes differ, so the trees are not the same.

p = [1,2,1], q = [1,1,2] returns false

The shapes match, but p's left child is 2 while q's left child is 1. One mismatched value is enough to return false.

Constraints

0 <= number of nodes <= 100

Hints

Hint 1

Two trees are equal exactly when their roots match and which two pairs of subtrees match?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Walk both trees in lockstep with recursion. If both nodes are null they match; if exactly one is null the shapes differ, so return false. Otherwise the values must be equal and both the left pair and the right pair of subtrees must match. The && short-circuits, so the walk stops at the first difference. O(n) time, where n is the size of the smaller tree, and O(h) space for the call stack.

Time

O(n)

Space

O(h)

Pitfall

Reading .val before handling nulls, or returning true when only one side is null. [1,2] and [1,null,2] hold the same values, so only the null checks catch that their shapes differ.

Solutions

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val
            && isSameTree(p.left, q.left)
            && isSameTree(p.right, q.right);
    }
}

class Solution:
    def isSameTree(self, p, q) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        return (p.val == q.val
                and self.isSameTree(p.left, q.left)
                and self.isSameTree(p.right, q.right))