DSA Tracker

Visualize

Symmetric Tree

Two pointers walking a tree in opposite directions

time O(n)space O(h)

Symmetry is not a property you can check on one node at a time. It is an equality between two subtrees walked in opposite directions: the left subtree's LEFT child must match the right subtree's RIGHT child, and the left subtree's RIGHT child must match the right subtree's LEFT child. So the helper takes a pair of nodes, not one. Two missing nodes are a match, one missing node is a mismatch, and a value mismatch ends it. Otherwise recurse on the outer pair and the inner pair, and the answer is true only if both are.

Details

Animated on: Tree [1, 2, 2, 3, 4, 4, 3]. Is it a mirror of itself around its centre? Answer: true.

Problem:Symmetric TreeEasy

Two pointers walking a tree in opposite directions

step 1 / 9

3
2
4
1
4
2
3

Call stack

isSymmetric(1)

isSymmetric(1): a tree is symmetric when its LEFT subtree is the mirror image of its RIGHT subtree. The root is on the axis and needs no partner, so the whole question becomes isMirror(2, 2).

Pseudocode
1FUNCTION isSymmetric(root)
2  RETURN isMirror(root.left, root.right)
3FUNCTION isMirror(a, b)
4  IF a = null AND b = null: RETURN true
5  IF a = null OR b = null OR a.val != b.val: RETURN false
6  outer <- isMirror(a.left, b.right)
7  inner <- isMirror(a.right, b.left)
8  RETURN outer AND inner

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. isSymmetric(1): a tree is symmetric when its LEFT subtree is the mirror image of its RIGHT subtree. The root is on the axis and needs no partner, so the whole question becomes isMirror(2, 2).
  2. isMirror(2, 2): values match, but equal values alone prove nothing. Both subtrees under them must ALSO mirror, so recurse on the OUTER pair first: 2.left = 3 against 2.right = 3.
  3. isMirror(3, 3): values match and both are leaves, so the outer pair (null, null) and the inner pair (null, null) each hit the base case and return true. Two empty subtrees are trivially mirrors of each other.
  4. isMirror(3, 3) returns outer AND inner = true. Nodes 3 and 3 are done; the verdict climbs one frame up the stack.
  5. Outer pair returned true. Now the INNER pair: 2.right = 4 against 2.left = 4. Left goes right, right goes left. Comparing 2.left with 2.left instead would test whether the two subtrees are identical, which is a different question.
  6. isMirror(4, 4): values match and both are leaves, so the outer pair (null, null) and the inner pair (null, null) each hit the base case and return true. Two empty subtrees are trivially mirrors of each other.
  7. isMirror(4, 4) returns outer AND inner = true. Nodes 4 and 4 are done; the verdict climbs one frame up the stack.
  8. isMirror(2, 2) returns outer AND inner = true. Nodes 2 and 2 are done; the verdict climbs one frame up the stack.
  9. isMirror(2, 2) came back true, so isSymmetric returns true. Every node was touched exactly once in a pair, O(n) time, with the stack never deeper than the tree height, O(h) space.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Symmetric Tree in the editorAll Binary Trees problemsBack to roadmap