Difficulty: EasyTrees

Same Tree

Problem in Plain English

Given the roots of two binary trees p and q, return true when both trees share the same structure and the same values at every position. Two empty trees count as identical.

Problem Statement

Given the roots p and q of two binary trees, check whether they are the same tree.

Two trees are the same when they are structurally identical and every pair of nodes in matching positions holds equal values. Two empty trees are the same.

Constraints

Each tree contains between 0 and 100 nodes.
Node values lie between $-10^4$ and $10^4$ , inclusive.
Inputs are ordinary binary trees: no cycles or shared children. Array examples use level order with null for a missing child.

Examples

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: true

Both trees place 1 at the root with 2 left and 3 right.

Example 2

Input: p = [], q = []
Output: true

Both roots are absent. There is no position at which shape or value differs, so two empty trees match.

Example 3

Input: p = [1,2], q = [1,null,2]
Output: false

2 is a left child in p but a right child in q, so the structures differ.

Example 4

Input: p = [1,2,1], q = [1,1,2]
Output: false

The shapes match but the children hold swapped values.

Intuition

Equal roots are only the first check: every left and right position must also agree. In Example 1, pair 1 with 1, then 2 with 2 and 3 with 3; the empty child slots must match too. Equal values reached in different positions do not make identical trees.

Approaches

Pair Queue Check

Solution Details

Reveal Pair Queue Check: intuition, complexity, and code

Intuition

Walk both trees side by side with a queue of node pairs, rejecting the first pair that mismatches in shape or value. Pairing keeps the positions aligned, but the queue must buffer a full level of pairs at once.

Step-by-Step Logic

Queue the pair (1,1) from p = [1,2,3] and q = [1,2,3].
Dequeue (1,1): values match, so queue (2,2) and (3,3).
Dequeue (2,2): values match, so queue its two empty child pairs.
Dequeue (3,3): values match, so queue its two empty child pairs.
Every remaining pair holds two empty slots, so return true.

Why It Works

The queue invariant is that every stored pair represents the same path from the two roots. Initially this holds for the roots. Matching nonempty nodes enqueue corresponding left and right children, preserving the invariant. Two empty slots agree; exactly one empty slot or unequal values proves a mismatch. If the queue empties without a mismatch, every reachable position has agreed, which is precisely tree equality.

Dry Run

Pair Queue Check: variable states at each step
head / action	current pair	remaining queue after action	decision
initialize `head = 0`	none	`[(1,1)]`	comparison pending
`0 -> 1`	`(1,1)`	`[(2,2),(3,3)]`	equal roots; append child pairs
`1 -> 2`	`(2,2)`	`[(3,3),(null,null),(null,null)]`	equal left nodes; append both empty slots
`2 -> 3`	`(3,3)`	`[(null,null),(null,null),(null,null),(null,null)]`	equal right nodes; append both empty slots
`3 -> 4`	`(null,null)`	`[(null,null),(null,null),(null,null)]`	both absent; append nothing
`4 -> 5`	`(null,null)`	`[(null,null),(null,null)]`	both absent; append nothing
`5 -> 6`	`(null,null)`	`[(null,null)]`	both absent; append nothing
`6 -> 7`	`(null,null)`	`[]`	both absent; append nothing
finished	none	`[]`	return `true`

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the total number of input nodes. Each matching nonempty pair creates two child pairs; each pair is processed once with constant work. Java/Python remove pairs and need O(w + 1) live queue storage for maximum width w. JavaScript advances a head index, retaining O(n + 1) pair arrays until return; this avoids the repeated shifting cost of Array.shift(). All versions allocate O(n + 1) pair objects over the run and never copy or mutate tree nodes. The displayed bounds cover nonempty inputs; empty inputs use constant work and storage.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Deque;3
4class TreeNode {5    int val;6    TreeNode left, right;7    TreeNode(int val) { this.val = val; }8}9
10class Solution {11    public boolean isSameTree(TreeNode p, TreeNode q) {12        Deque<TreeNode[]> queue = new ArrayDeque<>();13        // The pair array is non-null even when both contained nodes are null.14        queue.addLast(new TreeNode[]{p, q});15        while (!queue.isEmpty()) {16            TreeNode[] pair = queue.removeFirst();17            TreeNode a = pair[0], b = pair[1];18            if (a == null && b == null) continue;19            if (a == null || b == null || a.val != b.val) return false;20            // Preserve position: compare left with left and right with right.21            queue.addLast(new TreeNode[]{a.left, b.left});22            queue.addLast(new TreeNode[]{a.right, b.right});23        }24        return true;25    }26}

Hints

Hint 1

Visit matching positions together: the left child of one with the left child of the other, and likewise for the right.

Hint 2

Two empty slots in the same position are fine, but one empty slot against a real node ends the check.

Hint 3

Equal values still need equal subtrees, so confirm the current pair and recurse into both child pairs.

Edge Cases

Two empty trees match without any comparison.
One empty tree against a non-empty tree mismatches at the very first pair.
Equal values in mirrored positions still mismatch because the structure check pairs left with left.

Common Mistakes and Interview Tips

Reading .val before ruling out empty nodes, which crashes on the first missing child.
Comparing only values while ignoring shape, which wrongly accepts mirrored placements.
Returning true after the roots match without checking the subtrees below.
Comparing preorder value lists without null markers loses shape: [1,2] and [1,null,2] both visit values 1,2.
Using JavaScript Array.shift() repeatedly can add quadratic movement of queue entries; advance a head index.
Using OR to combine child matches accepts a tree when only one side agrees.

Key Takeaway

Dual-tree questions stay aligned by carrying both nodes together, whether as a recursive pair of arguments or as pairs in a queue.