Same Tree
MediumBoth null, or both equal with matching subtrees
Problem
Return whether two binary trees are structurally identical with equal values.
Walk both trees together; they're identical only if every matching node agrees in value and shape.
The idea
Two trees are identical when both are null, or both exist with the same value and identical left and right subtrees. The recursion mirrors the definition exactly and short-circuits at the first mismatch.
The trick
- One null and one non-null is an immediate false.
- Compare structure and value together, not one then the other.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,3] and [1,2,3] Values: 1, 2, 3.
1same(a,b):2 if !a and !b: true3 if !a or !b or a.val!=b.val: false4 return same(a.l,b.l) and same(a.r,b.r)Input
- array
- [1, 2, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- p = [1,2,3], q = [1,2,3]
- Output:
- true
- Explanation:
- Same shape and values.
Example 2
- Input:
- p = [1,2], q = [1,null,2]
- Output:
- false
- Explanation:
- Different shapes → false.
Example 3
- Input:
- p = [1,2,1], q = [1,1,2]
- Output:
- false
- Explanation:
- Values differ → false.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.