Same Tree

Difficulty: Easy

Problem

Given the roots of two binary trees p and q, return true if and only if the trees are the same. Two trees are the same when they are structurally identical AND every pair of corresponding nodes holds equal values. This is your first TWO-tree recursion: instead of walking one tree, you walk both at once.

Example

Input: p = [1,2,3], q = [1,2,3]
Output: true
Explanation: Both trees have root 1, left child 2, and right child 3. Every position that exists in p exists in q, and every pair of corresponding nodes holds the same value.

Brute-force approach

There is no meaningful 'brute force vs optimal' split here — comparing the trees pair by pair IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: Never compare trees — compare PAIRS of nodes. Move through p and q with identical steps and ask three tiny questions at every stop; the AND of all those answers is the answer for the whole trees.

Walk both trees at the same time, always standing on a PAIR of corresponding nodes. Each pair answers three quick questions: both null → true, one null → false, values differ → false. If all three pass, recurse on the left pair and the right pair, joined by AND.

Steps

  1. Start with the pair (p, q) — the two roots
  2. If both nodes are null, return true — matching absence is a match
  3. If exactly one is null, return false — the shapes differ at this spot
  4. If the values differ, return false — same position, different data
  5. Recurse on (p.left, q.left) AND (p.right, q.right) — both sides must match

Time complexity: O(n) · Space complexity: O(h)