Same Tree

Difficulty: Easy

Problem

You are given the roots of two binary trees, p and q. Return true only if the trees are identical: they must have the same shape, and every pair of nodes in matching positions must store the same value. This is your first TWO-tree recursion: instead of walking one tree, you walk both at once.

Example

Input: p = [5,1,8,null,3], q = [5,1,8,null,3]
Output: true
Explanation: Both trees have root 5, left child 1, and right child 8, and in both the node 1 has only a right child 3. Every position that exists in p exists in q with 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

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

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

Pseudocode

function isSameTree(p, q):
    if p is null and q is null:
        return ____
    
    if p is null or q is null:
        return ____
    
    if p.val != q.val:
        return false
    
    return isSameTree(____, ____) and
           isSameTree(____, ____)

Hints

Both missing: the two trees AGREE there's nothing at this spot. Is agreement a match or a mismatch?
Exactly one missing: one tree has a branch where the other has a gap. Can the shapes still be identical?
Lock-step pairing: p's LEFT child walks with q's LEFT child, and right walks with right, fill in the pairs accordingly
Why AND and not OR? BOTH subtree comparisons must succeed. One false anywhere sinks the whole answer

Complexity questions

Trees p and q have n and m nodes. The runtime is O(min(n, m)). Why can the walk finish without touching all of the larger tree?

Because it short-circuits: the walk stops at the first mismatch, and wherever the smaller tree runs out, a one-null check ends that branch. Each recursive call consumes one PAIR, a node from each tree, so there can never be more real pairs than the smaller tree has nodes. Wherever the smaller tree runs out, the one-null check returns false without going deeper, and a value mismatch near the root stops things even sooner. Only when the trees are identical do we visit everything, and then n = m, giving O(n).

What is the space complexity of the recursive solution?

O(h): the recursion call stack grows as deep as the tree. We create nothing (no arrays, no copies) but recursion isn't free. The call stack holds one frame per pair along the current path from the roots downward: O(log n) deep for balanced trees, O(n) for a completely skewed one. That's O(h), where h is the height of the trees we actually descend.

Both trees have a MILLION nodes each, but their root values differ (say 5 vs 6). How many pairs does the algorithm compare?

Exactly one: the root pair fails the value check and everything stops. The very first call compares the pair (5, 6): both nodes exist, the values differ, and False comes back before a single recursive call is made. Two million nodes, one comparison. In practice the runtime is 'time to the first mismatch', not 'size of the trees'.

Could we instead record each tree's preorder traversal into an array and just compare the two value arrays?

No: different shapes can produce the same traversal: [1,2] and [1,null,2] both give preorder [1, 2]. A values-only traversal throws away the structure. p = [1,2] (2 on the left) and q = [1,null,2] (2 on the right) both flatten to preorder [1, 2], yet they are NOT the same tree. You could rescue the idea by recording null markers too, but at that point the lock-step walk is simpler, stops earlier, and uses no extra arrays.

Check your understanding of Same Tree

What must match for two trees to count as 'the same'?

BOTH the structure and the value at every corresponding position. Sameness is a double requirement. The shapes must be identical. Every node in p has a partner at the exact same position in q, AND each pair of partners must hold equal values. Fail either requirement anywhere in the trees, and they are not the same.

p = [1,2] puts node 2 as the LEFT child of 1. q = [1,null,2] puts node 2 as the RIGHT child. Are these trees the same?

No: the values match but the STRUCTURE differs: node 2 hangs on different sides. Both trees hold the same values, but stand at the roots' left children: p offers node 2 while q offers nothing. That structural gap alone makes the answer false, positions matter, not just values. This is exactly the judge's second test case, so keep it in mind!

At each step of the algorithm, what do we actually compare?

A PAIR of corresponding nodes (one from p, one from q) visited in lock-step. We never compare 'trees' directly: we compare node PAIRS. Start with the pair (p's root, q's root), then walk both trees with identical moves: p.left pairs with q.left, p.right pairs with q.right. Each pair is a tiny question you can answer instantly.

The walk reaches a spot where p's node AND q's node are both null. What's the verdict for this pair?

true, matching absence is a match: both trees agree there's nothing here. Both trees say 'nothing here', and agreeing is matching! Returning true for the both-null pair is the base case that lets two equal trees finish with true: every branch of the walk eventually ends in matching nothingness below the leaves.

Why can we stop the moment ONE pair fails to match?

Because the final answer is an AND across every pair: a single false sinks the whole result. The overall answer is pair AND pair AND pair... across every position. Once any single pair reports false, no amount of matching elsewhere can rescue the result. That's why the code returns false immediately, and why the AND between the recursive calls short-circuits, skipping the right subtree entirely if the left already failed.