Are Two Trees Identical?

L7 Medium Trees

Concept

Structural equality on trees is a direct recursive comparison: values match and both subtrees match.

Given the roots of two binary trees p and q, return true if they are structurally identical — same shape, same values at every corresponding position.

Examples

▸ p = [1, 2, 3], q = [1, 2, 3]

→ true

▸ p = [1, 2], q = [1, nil, 2]

→ false

▸ p = [], q = []

→ true

Progressive Hints

Hint 1 · Nudge

Trees match only when both nodes are empty, or both present with equal values and matching children.

Hint 2 · Plan

If both roots are nil, return true. If exactly one is nil, return false. Compare the values, then recurse on both left subtrees and both right subtrees. Every check must pass.

Hint 3 · Approach

If p is nil and q is nil, return true. If one is nil, return false. If p.val != q.val, return false. Return sameTree(p.left, q.left) and sameTree(p.right, q.right).

Output

// Run your code to see the output here.