Same Tree

Given two binary trees, return true if they are structurally identical and have the same node values.

Why this is worth learning

Value sequences alone omit shape. Equality must pair corresponding child positions, including nil positions.

Before coding: one-minute experiment

Are a root 1 with left child 2 and a root 1 with right child 2 the same tree?

Function signature

func IsSameTree(p *TreeNode, q *TreeNode) bool

Inputs / outputs

• p, q: roots of two trees.
• Return: true if identical, else false.

Example

Tree1: 1,2,3
Tree2: 1,2,3
Output: true

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Comparing sets or traversal values throws away which child position holds each value. For example, a lone left child and a lone right child can give the same preorder values. Compare the structures directly by pairing corresponding nodes. Two absences match; one absence and one node do not; two nodes match only when their values and both child pairs match. Each recursive call answers the original question for a smaller pair of subtrees, so no unrelated height or value summary can replace the structure comparison.

Invariant: the function returns true iff the two subtrees are identical.

Algorithm (step-by-step)

1. If both nodes are nil, return true.
2. If exactly one is nil, return false.
3. If values differ, return false.
4. Recursively compare left children and right children.

Correctness sketch

Two nil roots describe equal empty trees. Exactly one nil root describes different shapes. For two real roots, equality requires equal values and equality of their corresponding left subtrees and right subtrees. These conditions are necessary because any structural equality preserves each child position. They are sufficient because equal roots with equal corresponding subtrees can be combined into identical whole trees. Structural induction proves the recursive test. A mismatch can return early without changing either tree.

Trace (hand walkthrough)

Example input:
Tree1: 1,2,3
Tree2: 1,2,3
Output: true

Walk:
- compare root: 1==1
- compare left: 2==2; compare right: 3==3
- all corresponding children nil -> true

Pitfalls to avoid

• Checking values before nil checks (can panic).
• Comparing only values without verifying structure.

Debugging lens

Compare serialization with explicit nil markers as an independent oracle. Tests using only preorder values can mistakenly consider different shapes equal.

Complexity

• Time: O(n).
• Extra space: O(h) recursion depth.

Implementation notes (Go)

• Use straightforward recursion; an iterative stack-based comparison also works.

Reconstruction checkpoint

Tree A is root 2 with only left child 6. Tree B is root 2 with only right child 6. Both preorder value lists are [2,6]. Are they the same, and what information would serialization need to preserve?

Return to Binary Tree General · Module quiz