Same Tree

easyTrees: Traversal27 stepsJava · Python · C++

Two trees are the same when they have the same shape and values. Walk both at once: two nulls match, one null doesn't, and otherwise the values must match and both pairs of subtrees must be the same.

▶ Watch the animated trace

Traced input: p = [1, 2, 3], q = [1, 2, 3] → true. Original problem: neetcode.io/problems/same-binary-tree

Complexity

BestO(1)

AverageO(n)

WorstO(n)

SpaceO(h)

Stops at the first difference.

Key idea

Compare structure and value at each pair of nodes.
Both null → true; exactly one null → false.
&& short-circuits, so a mismatch on the left skips the right side.

Common mistakes

Comparing only in-order traversals: different shapes can give the same sequence.
Checking p.val == q.val before checking for null.

Solution

Java

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

Python

def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q: return True
    if not p or not q:
        return False
    return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

C++

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) {
        return false;
    }
    return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Different shape 2 is a left child in p and a right child in q.	`p = [1, 2], q = [1, null, 2]`	`false`
Different values The left children differ.	`p = [1, 2, 1], q = [1, 1, 2]`	`false`
Both empty Two nulls match.	`p = [], q = []`	`true`
One empty Only one side has a node.	`p = [1], q = []`	`false`