Check if two trees are identical or not
MediumSame value, same shape, recursively
Problem
Return whether two binary trees are identical in structure and values.
Walk both trees together; they're identical only if every matching node agrees in value and shape.
The idea
Two trees match when both are null, or both are non-null with equal values and matching left and right subtrees. The structure of the check mirrors the structure of the data exactly.
The trick
- Both null is true; one null is false.
- O(n) and it short-circuits on the first difference.
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==null and b==null: return true3 if a==null or b==null or a.val!=b.val: return false4 return same(a.left,b.left) and same(a.right,b.right)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.