DSA problem
Same Tree
Given the roots p and q of two binary trees, decide whether they are structurally identical and node-wise equal. The trees are considered the same when they have exactly the same shape and every corresponding pair of nodes carries the same value.
This is the canonical introductory tree problem because the recurrence is so clean. Two trees are the same iff: (1) both roots are null (vacuously equal), or (2) both roots are non-null, the values match, and the left subtrees are the same and the right subtrees are the same. Any other combination — one null and one non-null, or differing values — means the trees diverge.
The structure of the recurrence is preorder by design: you compare the current pair of roots before descending into their children, short-circuiting the recursion the moment a mismatch is found. This early termination matters in practice — for two random large trees, a difference is often found near the top.
The natural implementation is a four-line recursion. An iterative version using a stack (or queue) of pairs is equally O(n) time and works the same way; the recursive form is preferred for clarity unless you specifically need to avoid stack frames. Either way, time is O(n) where n is the size of the smaller tree once divergence is detected, and space is O(h) for the recursion stack.
Examples
p = [1,2,3], q = [1,2,3]truep = [1,2], q = [1,null,2]falsep = [1,2,1], q = [1,1,2]falseConstraints
- The number of nodes in each tree is in the range [0, 100].
- -10^4 <= Node.val <= 10^4
- Both inputs are valid binary trees.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.