Trees · LC #100
Same Tree
Determine if two binary trees are structurally identical with the same node values at every position. Simultaneous DFS on both trees checks structure and values together.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given the roots of two binary trees `p` and `q`, write a function to check if they are the same. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Sample I/O
Input: p=[1,2,3], q=[1,2,3] Output: true Input: p=[1,2], q=[1,null,2] Output: false
Intuition
How to Think About It
Intuition
Recursion works naturally because two trees are the same iff their roots match AND their left subtrees are the same AND their right subtrees are the same - a direct structural decomposition with clear base cases at null nodes.
Core Concept
Simultaneously traverse both trees: if both nodes are null → true (both ended together). If one is null and the other is not → false (structural mismatch). If values differ → false. Otherwise recurse on left pair and right pair with logical AND.
When to use
Tree equality checks, subtree matching (building block for Subtree of Another Tree), deep-clone verification.
When NOT to use
When you only need value equality without structural check (serialization-based comparison may be simpler for some variants).
Key Insights
What to Know Cold
- Short-circuit AND: if left subtrees differ, right subtrees are never checked.
- The three-condition check order matters: null-both → null-one → value differ.
- Iterative variant uses two stacks in lockstep.
- Building block for isSubtree: call isSameTree at each node of the host tree.
- Works for any value type - generalize by replacing `val` equality with a comparator.
2 examples
Worked Examples
Identical trees
p=[1,2,3] and q=[1,2,3] - same structure and same values.
Recurse: (1,1) match → (2,2) match → (null,null) true, (null,null) true → true; (3,3) match → true. All true.
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}Output: true
Shows the three-guard pattern reused in subtree and symmetry problems.
Structural mismatch
p=[1,2] vs q=[1,null,2] - left-child vs right-child placement differs.
At root (1,1): match. Left: (2, null) → one null → false. Short-circuit → false.
Output: false
Highlights that structural position matters, not just value presence.