Binary Tree Zigzag Level Order Traversal

Medium#103tree nodes

Write down the values of a binary tree level by level, turning direction on every level: the top level left to right, the next one right to left, and so on. Our example: the tree [7, 4, 9, none, 5, 1, 11] in level order — the answer is [[7], [9, 4], [5, 1, 11]].

103 Binary Tree Zigzag Level Order TraversalWalkthrough · 1×

Example: read [7, 4, 9, none, 5, 1, 11] level by level, turning on every level.

7495111levelleft to right—queuefront on the left—
not reachedwaiting in the queuecurrent, just writtendone

The tree is not empty

01/56
restart · back · play · step
Speed
1function zigzagLevelOrder(root):
2 if root is none:
3 return []
4 result = []
5 queue = [root]
6 leftToRight = true
7 while queue is not empty:
8 level = []
9 size = queue.size
10 repeat size times:
11 node = queue.popFront()
12 if leftToRight:
13 level.addBack(node.val)
14 else:
15 level.addFront(node.val)
16 for each child of node, left first:
17 queue.pushBack(child)
18 result.add(level)
19 leftToRight = not leftToRight
20 return result
state
result
–
queue
–
leftToRight
–
level
–
size
–
node
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The queue is never turned around: children always go in left first, so each level comes out of it left to right, as in plain level order.
  2. On a right-to-left level each value is put in front of the ones before it, so the level is written reversed at no extra cost.
  3. leftToRight flips after every level, so the directions alternate starting with left to right.

Complexity

Time O(n): each node enters and leaves the queue once, and addFront takes one step on a double-ended list. Memory O(n): the answer holds every value, the queue at most about two levels.

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.