Same Tree

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

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)

Recursively compare nodes:

• If both are nil, they match.
• If only one is nil, not the same.
• Values must match, and left/right subtrees must match.

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

• Invariant: the function returns true iff the two subtrees are identical.
• Base cases handle nil/leaf nodes correctly.
• Recursive calls return correct results for subtrees (induction).
• Combining subtree results yields the correct answer for the current node.

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.

Complexity

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

Implementation notes (Go)

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