Example 1
ready- Input
p = [ 1, 2, 3 ] q = [ 1, 2, 3 ]- Expected
true- Why
- every value and child position matches
Same Tree
25 min · isSameTree()Two company org charts can contain the same names and still describe different teams: where each person sits matters as much as the names themselves.
Given the roots p and q, return true only when the two binary trees are
structurally identical — every corresponding position is either empty in both trees
or holds nodes with the same value.
Keep both parts of that rule in view:
- Equal values in a different shape don't make the trees equal.
- Matching shapes with one different value don't make them equal.
- Two empty trees are the same.
- One empty tree and one non-empty tree are different.
Constraints
0 <= number of nodes in each tree <= 10_000-1_000 <= node.val <= 1_000
Hints
Preserve the gaps
If you serialize each tree level by level, keep markers for missing children. Without those gaps, a left child and a right child can look identical.
Compare a pair of positions
For two current nodes, there are three useful cases: both are absent, exactly one is absent, or both exist. Decide each case before moving deeper.
All three checks must survive
When both nodes exist, their values must match, their left subtrees must match, and their right subtrees must match. One failed check settles the answer.
Follow-up
Could you perform the simultaneous comparison with an explicit stack so a very deep tree never depends on the language's recursion limit?
Visible cases
Examples
Example 2
ready- Input
p = [ 1, 2 ] q = [ 1, null, 2 ]- Expected
false- Why
- the value 2 sits on opposite sides of the roots
Example 3
ready- Input
p = [] q = []- Expected
true- Why
- two empty trees have the same shape and values
Interview signal
Asked at
AmazonGoogle
Compare serializations — turn shape into data
Serialize both trees in level order, including None for missing children. Those markers
carry the shape: [1, 2] and [1, None, 2] contain the same values but remain different.
from collections import deque
def serialize(root: TreeNode | None) -> list[int | None]:
if root is None:
return []
values: list[int | None] = []
queue = deque([root])
while queue:
node = queue.popleft()
if node is None:
values.append(None)
continue
values.append(node.val)
queue.append(node.left)
queue.append(node.right)
while values and values[-1] is None:
values.pop()
return values
def is_same_tree(p: TreeNode | None, q: TreeNode | None) -> bool:
return serialize(p) == serialize(q)Time O(n) — both trees are serialized once, where n is their combined node count.
Space O(n) — the two serialized arrays and queues grow with the input.
Simultaneous depth-first walk — compare only what you need
You don't need to store either whole tree. Compare one pair of positions:
- two absent nodes match;
- exactly one absent node fails;
- two real nodes match only if their values and both child pairs match.
def is_same_tree(p: TreeNode | None, q: TreeNode | None) -> bool:
if p is None or q is None:
return p is q
return (
p.val == q.val
and is_same_tree(p.left, q.left)
and is_same_tree(p.right, q.right)
)The and chain short-circuits as soon as one value or subtree differs, so a mismatch
near the root avoids unnecessary work.
Time O(n) — in the worst case you inspect every corresponding node pair.
Space O(h) — recursion keeps one path of height h on the call stack.
Python can raise RecursionError on a valid 1,200-node line. The same comparison stays
stack-safe when you store node pairs yourself:
def is_same_tree_iterative(p: TreeNode | None, q: TreeNode | None) -> bool:
stack = [(p, q)]
while stack:
left, right = stack.pop()
if left is None or right is None:
if left is not right:
return False
continue
if left.val != right.val:
return False
stack.append((left.left, right.left))
stack.append((left.right, right.right))
return TrueThat explicit stack preserves O(n) time and O(h) space without using Python's call stack.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
true
Run: visible + custom · Submit: full suite