100. Same Tree
easyDecide whether two binary trees are structurally identical with the same values at every position. Pure recursion with three base cases.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
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
Example 1
p = [1,2,3], q = [1,2,3]trueExample 2
p = [1,2], q = [1,null,2]falseExample 3
p = [1,2,1], q = [1,1,2]falseSolve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Three base cases: both null (equal), one null one not (unequal), both non-null with different values (unequal).
Hint 2
Otherwise recurse on left and right subtrees.
Hint 3
AND-combine: same(p.left, q.left) AND same(p.right, q.right).
Solution approach
Reveal approach
Recursive structural compare. Base cases first: if both p and q are null, return true; if exactly one is null, return false; if p.val != q.val, return false. Otherwise return sameTree(p.left, q.left) AND sameTree(p.right, q.right). Each node is visited at most once per tree, so O(n) time. Recursion stack is O(h) where h is the tree height — up to O(n) for skewed trees.
Complexity
- Time
- O(n)
- Space
- O(h)
Related patterns
- dfs
- recursion
Related problems
- 101. Symmetric Tree
- 572. Subtree of Another Tree
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
Practice these live with InterviewChamp.AI
Drill Same Tree and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →