Same Tree
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber
Problem
Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two trees are the same if they are structurally identical and have the same node values.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Apple | Easy | View all Apple questions → |
| Uber | Easy | View all Uber questions → |
How to Think About It
Recursive: both null → same. One null, one not → different. Values differ → different. Otherwise, recurse on left children and right children.
The three checks in order: (1) are both nodes null? (2) is one null and the other not? (3) do values differ? If none of these, recurse.
BFS alternative: use two queues, push roots of both trees. Process both queues simultaneously. Compare values and children positions.
Visual walkthrough for trees: 1 1
/ / \n 2 3 2 3
sameTree(1,1): values match. Recurse left and right.
sameTree(2,2): values match. Both leaves. Recurse (null,null) twice → true.
sameTree(3,3): values match. Both leaves. Recurse (null,null) twice → true.
Result: true.
Edge cases: both null (true), one null (false), different structures (false), same structure different values (false).
Optimal Approach
Recursive DFS:
Step 1: If both p and q are null → return true.
Step 2: If one is null and the other isn't → return false.
Step 3: If values differ → return false.
Step 4: Recurse: sameTree(p.left, q.left) AND sameTree(p.right, q.right).
The order matters: check null first (base case), then values, then recurse.
Time: O(n) — visit every node once. Space: O(h) — recursion stack.
What Trips People Up in Real Interviews
Only checking values, not structure. Two trees can have the same values but different structures. Check both.
Forgetting to check if both nodes are null. Two null nodes are considered the same tree.
Not handling the case where one node is null and the other isn't. This means the trees are different.
Confusing "same tree" with "identical structure." Same tree means both structure AND values must match.
Not checking values after confirming both nodes exist. After ruling out null mismatches, you must compare p.val != q.val before recursing — skipping this gives wrong results for same-structure different-value trees.
Solution Code
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)Frequently Asked Questions
What is the Same Tree problem?
Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two trees are the same if they are structurally identical and have the same node values.
How do you solve Same Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Same Tree?
Same Tree is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a easy difficulty problem.
What are common mistakes on Same Tree?
- Only checking values, not structure. Two trees can have the same values but different structures. Check both.
- Forgetting to check if both nodes are `null`. Two `null` nodes are considered the same tree.
- Not handling the case where one node is `null` and the other isn't. This means the trees are different.
- Confusing "same tree" with "identical structure." Same tree means both structure AND values must match.
- Not checking values after confirming both nodes exist. After ruling out `null` mismatches, you must compare p.val != q.val before recursing — skipping this gives wrong results for same-structure different-value trees.