Check whether two trees are identical
Filed under Microsoft
Free read 3 of 3Confirm what constitutes equality (both structure and node values must match).
The question
Given the roots of two binary trees `p` and `q`, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Constraints
- The number of nodes in both trees is in the range [0, 100].
- -10^4 <= Node.val <= 10^4
Examples
- Input
- p = [1,2,3], q = [1,2,3]
- Output
- true
- Why
- Both trees have the exact same structure and node values.
- Input
- p = [1,2], q = [1,null,2]
- Output
- false
- Why
- Structure differs as the right child is present in one and left in the other.
Approach
Confirm what constitutes equality (both structure and node values must match).
Serialize both trees into string representations or arrays (handling nulls) and compare the results.
Use recursive DFS. If both nodes are None, return True. If one is None or values differ, return False. Recursively compare left and right subtrees.
Both trees are empty (None), or one tree is a subset of the other.
Solution
O(N) time where N is min number of nodes, O(N) space for recursion stack.
class Solution:
def isSameTree(self, p, q) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Tips
- What they are testing: Test with empty trees, trees of different heights, and trees with the same values arranged differently.
- Common mistake: Failing to check for null pointer exceptions when one node is None and the other is not.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.