Zigzag and spiral level order in Python

Why it matters

Level order traversal, from the level order lesson of this module, prints a tree one level at a time, and every level goes from left to right. That direction never changes. Some outputs need it to change: the first level goes left to right, the second goes right to left, the third goes left to right again, and so on. This pattern is called a zigzag. A row of seats that fills from one side on odd rows and from the other side on even rows is a zigzag. A printed page with a snake-shaped reading order is one too.

Some texts call the same output spiral order. This lesson uses both names for the same output.

The lesson shows two ways to produce it. The first is simple and easy to check. The second uses one deque for the whole traversal.

Words you will need

• Level: all nodes that are the same number of steps below the root. The root is the first level.
• Level order: visiting the nodes one level at a time, from top to bottom.
• Queue: a line where items join at the back and leave from the front. In Python, collections.deque is the queue, with append to join at the back and popleft to leave from the front.
• Deque: a double-ended queue. Items can be added or removed at either end. The word is pronounced "deck". In Python, collections.deque is a deque too.
• append, appendleft, pop, popleft: the four deque methods used in this lesson. append and appendleft add an item to the back or the front. pop and popleft remove the item at the back or the front and return it. Both pop and popleft raise an error when the deque is empty, so check while dq: first.
• list.reverse(): a method that reverses the order of a list in place.
• None: Python's value for "no object". A missing child is stored as None.
• Mutable and immutable sequence: a list can change after it is made. A tuple cannot. The mistakes section shows what happens when a tuple is changed.

Start with one tree

Take this tree. The numbers are the values stored in the nodes. The lines show which node is the parent of which.

            1
         /     \
        2       3
       / \     / \
      4   5   6   7
     /           \
    8             9

Read each level from left to right, then decide the direction for that level. Level 1 goes left to right. Level 2 goes right to left. Level 3 goes left to right again. Level 4 goes right to left.

So the answer for this tree is a list of four lists: [[1], [3, 2], [4, 5, 6, 7], [9, 8]].

The hard part is not the direction. The hard part is making sure you read the right nodes in the right order before the direction flips. Both methods below solve that.

The base: reading one level at a time

Level order uses a queue. Start with the root in the queue. Each step removes the node at the front, records its value, and adds its children to the back. Left child first, then right child.

The queue alone does not tell you where one level ends and the next starts. The trick is to read the queue's length before you start a level. At that moment the queue holds exactly the nodes of that level, and nothing else. Read exactly that many nodes. Their children join the back of the queue and form the next level.

The code below is the base that both methods share. It prints every level in the normal order. The lesson changes it in two different ways.

def level_order(root):
    result = []
    if root is None:
        return result
    queue = deque([root])
    while queue:
        size = len(queue)
        level = []
        for _ in range(size):
            n = queue.popleft()
            level.append(n.value)
            if n.left is not None:
                queue.append(n.left)
            if n.right is not None:
                queue.append(n.right)
        result.append(level)
    return result

The Node class used in every code sample in this lesson looks like this:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

The two methods below use the same Node class.

Approach 1: reverse every other level

The first method is the base with one extra step. Keep a flag that says which direction the current level goes. After you collect a level, if its direction is right to left, reverse the list. Then flip the flag.

def zigzag_reverse(root):
    result = []
    if root is None:
        return result
    queue = deque([root])
    left_to_right = True
    while queue:
        size = len(queue)
        level = []
        for _ in range(size):
            n = queue.popleft()
            level.append(n.value)
            if n.left is not None:
                queue.append(n.left)
            if n.right is not None:
                queue.append(n.right)
        if not left_to_right:
            level.reverse()
        result.append(level)
        left_to_right = not left_to_right
    return result

The reversal happens after the whole level is collected. This is important. The children of a level must be added to the queue in left-to-right order, because the next level depends on that order. Only the printed list is reversed. The queue is never touched by the reversal.

Worked example 1: the tree from the start

Trace the tree from the start. The queue column shows what the queue holds at the start of each level.

Level 2 is the first reversal. Its children were added to the queue while nodes 2 and 3 were read: 4 and 5 from node 2, then 6 and 7 from node 3. The level list [2, 3] is reversed to [3, 2] for printing only. The queue still holds [4, 5, 6, 7] in left-to-right order, which is what level 3 needs.

Running the function on this tree prints:

zigzag_reverse: [[1], [3, 2], [4, 5, 6, 7], [9, 8]]

The cost is one pass over the tree. Each node is added to the queue once and removed once, so the time is proportional to the number of nodes. The queue never holds more than the nodes of two neighbouring levels at once, so the extra space is about the width of the widest level.

Approach 2: one deque, read from both ends

The second method avoids reversing lists. It uses a deque and changes which end it reads from.

On a left-to-right level, the nodes sit in the deque from left to right. Take them from the front, so the left-most node is read first. Add each node's children to the back, left child first. Then the next level sits in the deque from left to right too.

On a right-to-left level, the nodes also sit in the deque from left to right, but we want to read the right-most node first. So take them from the back. The children of these nodes are the next level, and the next level is a left-to-right level. That level must be read from the front, starting with its left-most node. So we add the children to the front. For each node, add the right child first and the left child second. The left child ends up in front of the right child, and the children of the nodes that were read earlier, which sit further right, stay behind them.

A short summary of the rule:

• Left-to-right level: read from the front, add children to the back, left first.
• Right-to-left level: read from the back, add children to the front, right first.

def spiral_deque(root):
    result = []
    if root is None:
        return result
    dq = deque([root])
    left_to_right = True
    while dq:
        size = len(dq)
        level = []
        for _ in range(size):
            if left_to_right:
                n = dq.popleft()
                level.append(n.value)
                if n.left is not None:
                    dq.append(n.left)
                if n.right is not None:
                    dq.append(n.right)
            else:
                n = dq.pop()
                level.append(n.value)
                if n.right is not None:
                    dq.appendleft(n.right)
                if n.left is not None:
                    dq.appendleft(n.left)
        result.append(level)
        left_to_right = not left_to_right
    return result

The loop still runs size times for each level, and size is read before the level starts. This is what keeps the levels apart. The children of a right-to-left level go to the front of the deque, while the unread nodes of that level are still in the deque behind them. Because the loop takes only size nodes, it never takes a child by mistake.

Worked example 2: the same tree, one step at a time

Start with [1] in the deque. Each row shows the deque after the step.

Look at step 2 closely. Node 3 is read first because it is the right-most node of level 2. Its children are 6 on the left and 7 on the right. The right child is added to the front first, so the deque becomes [7, 2]. Then the left child is added to the front, giving [6, 7, 2]. The unread node 2 is still at the back, and its children will go in front of 6 and 7 in step 3.

Step 3 shows why the order works. Node 2 is further left than node 3, so its children must come before the children of node 3 when the next level is read from the front. Adding node 2's children to the front does that. The result after step 3 is [4, 5, 6, 7], which is level 3 in left-to-right order.

The function prints the same answer as approach 1:

spiral_deque:   [[1], [3, 2], [4, 5, 6, 7], [9, 8]]

Each node is added once and removed once, so the time is again proportional to the number of nodes. The deque holds at most the nodes of two neighbouring levels.

Worked example 3: missing children and a single node on a level

The first two examples are full in the middle. Real trees often have gaps. Here is a tree with one missing right child on level 2, and a level 4 that holds one node.

          1
        /   \
       2     3
      /     / \
     4     5   6
            \
             7

Use the same rules. Level 1 is [1], level 2 is read right to left, and so on.

• Level 1: [1], left to right.
• Level 2: nodes 2 and 3. Read right to left, so the printed list is [3, 2].
• Level 3: children are 4 (child of 2), 5 and 6 (children of 3). Read left to right, so the list is [4, 5, 6]. Node 2 has no right child, and node 5 has no left child, so the gaps do not affect the order.
• Level 4: node 7 is the only child, the right child of node 5. Read right to left, so the list is [7].

Both methods print the same answer. Here is the real output from running them on this tree:

T3 zigzag_reverse: [[1], [3, 2], [4, 5, 6], [7]]
T3 spiral_deque:   [[1], [3, 2], [4, 5, 6], [7]]

Single-node levels are a good test for your code. A level with one node is read the same way in both directions. A level with one node reads the same in both directions, so it tests the None checks, not the direction.

Testing both methods against each other

A good habit is to write both methods and compare them on random trees. Two methods built from different ideas that agree on thousands of random trees are very likely both correct. The program below builds 2,000 random trees with up to 40 nodes each and compares the two outputs. The random generator is seeded with random.Random(42), so the run is the same every time. A fixed seed makes a failure reproducible, which is useful when a test fails.

Output:

T3 zigzag_reverse: [[1], [3, 2], [4, 5, 6], [7]]
T3 spiral_deque:   [[1], [3, 2], [4, 5, 6], [7]]
zigzag_reverse: [[1], [3, 2], [4, 5, 6, 7], [9, 8]]
spiral_deque:   [[1], [3, 2], [4, 5, 6, 7], [9, 8]]
random trees checked: 2000, both approaches agree on 2000

Common mistakes

Mistake 1: reversing a tuple

A tuple is a sequence that cannot be changed after it is made. A level built as a tuple, for example by a helper that returns (3, 2), cannot be reversed in place. The code below tries to do that. The code is shown without the run mark because it stops with an error.

level = (3, 2)
level.reverse()

The output is:

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    level.reverse()
    ^^^^^^^^^^^^^
AttributeError: 'tuple' object has no attribute 'reverse'

The fix is to build the level as a list, which can be changed. Approach 1 does this already with level = []. A list also has reverse(), which a tuple does not.

Mistake 2: adding a missing child to the deque

A deque accepts None as an item, so the mistake does not stop at the add. It stops later, when the code takes the None out and reads an attribute of it. The code below adds a missing child without checking for it first. The code is shown without the run mark because it stops with an error.

from collections import deque
 
dq = deque()
dq.append(None)
n = dq.popleft()
print(n.value)

The output is:

Traceback (most recent call last):
  File "main.py", line 6, in <module>
    print(n.value)
          ^^^^^^^
AttributeError: 'NoneType' object has no attribute 'value'

The check if n.left is not None before each add stops this. Forgetting one of the two checks is a common cause of this error in both methods.

Mistake 3: adding children to the front on a left-to-right level

Approach 2 uses append on left-to-right levels and appendleft on right-to-left levels. Using appendleft on a left-to-right level is a mistake that does not crash. The code below is spiral_deque with one change: on a left-to-right level, the children are added to the front, as on a right-to-left level.

The output is:

wrong: [[1], [3, 2], [4, 8, 5, 6], [7], [9]]

The first two rows are right. The third row has node 8 in the middle, and the output has an extra level. When node 4 is read, its child 8 goes to the front, so the next read takes 8 before node 5, which was already waiting. When a zigzag output has the wrong nodes in a level, check which end each step reads from and which end it adds to.

Mistake 4: adding the children of the right-to-left branch to the back

The code below is the right-to-left branch of approach 2 with the children added to the back. This looks like a small change, but it breaks the order.

        else:
            n = dq.pop()
            level.append(n.value)
            if n.left is not None:
                dq.append(n.left)
            if n.right is not None:
                dq.append(n.right)

On the lesson's example tree, using this branch in place of the right one prints:

wrong branch on example: [[1], [3, 7], [2, 6, 9], [5, 4], [8]]

Level 2 is printed as [3, 7], but node 7 is not on level 2. When node 3 is read, its children 6 and 7 go to the back, behind node 2. The next read from the back takes node 7, a child of node 3, instead of node 2. The fix is to add them to the front, right child first.

Mistake 5: reading the length in the loop condition

If the loop reads len(dq) in its condition, the length changes while the loop runs, because the loop adds children. A for _ in range(len(dq)) line is safe, because range reads the length once, when the loop starts. A while loop that compares a counter with len(dq) on each pass is not safe. The function below uses that while form.

The output is:

while-length version: [[1, 2, 3, 4], [6, 5], [7, 8], [9]]

The loop takes node 1, and then node 2 and node 3 join the queue and are taken as well, because the length grew. The levels run together, and the first list holds four nodes. Read the size once, into a variable, before the loop starts, or use range(len(queue)).

Practice

Exercise 1: trace a tree

Use tree T3 from worked example 3. Write the zigzag output without running the code. Then check your answer by running zigzag_reverse on the tree.

Show the answer

The output is [[1], [3, 2], [4, 5, 6], [7]]. Level 2 is printed right to left, so it is [3, 2]. Level 3 is printed left to right, so it is [4, 5, 6]. Level 4 has one node, so it is [7]. The function prints the same list.

Exercise 2: a chain going right

Take a tree with three nodes in a chain. Node 1 is the root. Node 2 is its right child. Node 3 is the right child of node 2. What does zigzag_reverse return?

Show the answer

It returns [[1], [2], [3]]. Each level has one node, so reversing a one-node list changes nothing. The output is the same as the normal level order.

Exercise 3: an empty tree

What do the two functions return when the root is None? Explain why the code does not fail.

Show the answer

Both return an empty list, printed as []. The first check, if root is None, returns the empty result before the queue or deque is created. Without this check, the deque would start as [None], and the loop would then read an attribute of None.

Exercise 4: explain the child order

In approach 2, the right-to-left branch adds the right child first and the left child second, both with appendleft. Explain in plain words why the order matters. Then say what would happen if the two lines were swapped.

Show the answer

Each appendleft puts the new item in front of every item already there. The last item added ends up at the front. So adding the right child first and the left child second leaves the left child in front. The next level is read from the front, and it must start with the left-most node. If the two lines are swapped, the right child ends up in front, and the next level is read in the wrong order for a level that should go left to right.

Exercise 5: count the work

Approach 2 adds and removes the nodes of the tree from the deque. How many times is each node added to the deque, and how many times is it removed? What is the total time for a tree with n nodes?

Show the answer

Each node is added once, when its parent is read, and removed once, when it is read itself. The root is added once at the start and removed once. So each node is added once and removed once. The total work is proportional to n, so the time is O(n).

Summary

• A zigzag or spiral level order prints each level in the direction of its level number: odd levels left to right, even levels right to left.
• Read the length of the queue or deque before each level. That number is exactly the number of nodes in the level.
• Approach 1 collects each level in order and reverses the printed list on every other level. It is short and easy to check.
• Approach 2 uses one deque. It reads from the left end on left-to-right levels and from the right end on right-to-left levels. Its children go to the right end on the first kind of level and to the left end on the second kind.
• Both methods do one pass over the tree, so the time is O(n). A None check before each child is needed in both.