Symmetric Tree

Easy#101tree nodes

You get the root of a binary tree. Say whether it is symmetric: folded along a vertical line through the root, its left half lands exactly on its right half, value on value and empty on empty. Our tree: 8 with two children 6; the left 6 has children 5 and 7, the right 6 has children 9 and 5 — the answer is false: the outer 5s mirror each other, but 7 and 9 do not.

101 Symmetric TreeWalkthrough · 1×

Example: check whether a binary tree is a mirror image of itself: walk its two halves at once, the left one left to right and the right one right to left.

nonenonenonenonenonenonenonenone8665795mirror call stack, top on the righta, left—b, right—
not compared yetpair waiting on the call stackthe pair compared nowpair returned truepair returned falsenone: an empty child

Fold the tree along the middle: compare the two halves under 8, mirror(6, 6)

01/21
restart · back · play · step
Speed
1function isSymmetric(root):
2 return mirror(root.left, root.right)
3
4function mirror(a, b):
5 if a is none and b is none:
6 return true
7 if a is none or b is none or a.val != b.val:
8 return false
9 if not mirror(a.left, b.right):
10 return false
11 return mirror(a.right, b.left)
state
a
–
b
–
click a step to go back

← → step · space play/pause

Why it works

  1. Two sides mirror each other exactly when their roots are equal, the left side's left child mirrors the right side's right child, and the left side's right child mirrors the right side's left child.
  2. So the pairs cross: 5 on the far left meets 5 on the far right, the outer pair, and 7 meets 9 by the middle, the inner pair. A node is never compared with the one in the same place under the other 6.
  3. The first pair that differs returns false straight up, so the rest is never compared.

Complexity

Time O(n): each node is in at most one pair, and each pair is compared once. Memory O(h), where h is the height of the tree: the call stack holds one path of pairs.

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.