Leetcode 100: Same Tree

 

1. Problem Summary

You are given the roots of two binary trees p and q.
You must determine whether the two trees are the same.

Two binary trees are considered the same if:

• They are structurally identical (same shape), and

• Every corresponding node has the same value.

Input: roots p and q (each may be null)

Output: Boolean: true if the trees are identical, false otherwise.

Constraints:

• Each tree has 0 to 100 nodes.

• Node values are in [-104, 104].

2. Examples Explanation

Example 1:

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

Both trees:

• Root 1

• Left 2

• Right 3

Same structure and node values → true.

Example 2:

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

Trees:

• p:

• Root 1

• Left 2

• Right null

• q:

• Root 1

• Left null

• Right 2

Different structure (one left child vs one right child) → false.

Example 3:

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

Same shape, different node values (2 vs 1 in left/right positions) → false.

3. Approach

Pattern:

This is a straightforward tree comparison problem, solved via:

• DFS recursion (compare node by node), or

• BFS/DFS iterative (queue/stack).

Recursive DFS is the simplest and most idiomatic.

High-Level Idea (Recursive DFS):

To check if trees rooted at p and q are the same:

1. If both p and q are null → they are equal here → return true.

2. If one is null and the other is not → not equal → return false.

3. If both are non-null:

• Check values: p.val == q.val.

• Recursively check:

• Left subtrees: isSameTree(p.left, q.left)

• Right subtrees: isSameTree(p.right, q.right)

• Trees are same if values match AND both subtrees match.

No extra tricks needed; constraints are small.

Pseudo-code:

Complexity Analysis:

Let n be the number of nodes (max of nodes in the two trees).

• Time Complexity:

• We compare corresponding nodes once → O(n).

• Space Complexity:

• Recursion stack depth up to tree height h.

• Worst case skewed tree: O(n); balanced: O(logn).

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code