Same Tree

Easy#100tree nodes

You get the roots of two binary trees, p and q. Say whether they are the same tree: the same shape, with the same value in every matching place. Our trees: both are 5 with children 8 and 6; in p, 6 has a left child 4, in q, 6 has a right child 4 — the answer is false: the values are the same, but 4 sits on different sides.

100 Same TreeWalkthrough · 1×

Example: check whether two binary trees are the same: walk both at once and compare them place by place.

pqnonenonenonenonenone5864nonenonenonenonenone5864isSame call stack, top on the rightp5q5
not compared yetpair waiting on the call stackthe pair compared nowpair returned truepair returned falsenone: an empty child

p is 5, q is 5: not both none

01/27
restart · back · play · step
Speed
1function isSame(p, q):
2 if p is none and q is none:
3 return true
4 if p is none or q is none:
5 return false
6 if p.val != q.val:
7 return false
8 if not isSame(p.left, q.left):
9 return false
10 return isSame(p.right, q.right)
state
p
5
q
5
click a step to go back

← → step · space play/pause

Why it works

  1. Two trees are the same exactly when their roots are equal, their left subtrees are the same and their right subtrees are the same, so isSame answers for a pair of nodes from the answers for their pairs of children.
  2. An empty child has to meet an empty child: here every value matches, and only the pair (4, none) under 6 shows that the shapes differ.
  3. The first false goes straight back up through every call, so the rest of both trees is never compared.

Complexity

Time O(n), where n is the size of the smaller tree: each pair of places is compared at most once. Memory O(h), where h is its height: the call stack holds one path.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.