Binary Tree Zigzag Level Order Traversal

+10

You get a binary tree stored in the array root. The root sits at index 0, the children of index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries.

Return the node values level by level in zigzag order: the root's level from left to right, the next from right to left, and so on, alternating down to the deepest level. This is also called a spiral level order traversal.

Function

zigzagLevelOrder(root: integer-array) → integer-2d-array

rootinteger-array: the tree in heap order, with -1 for an empty spot
Returnsinteger-2d-array: one list of values per level, top level first, alternating between left to right and right to left

Constraints

1 ≤ root.length ≤ 32767
Each root[i] is -1 or a value with 0 ≤ root[i] ≤ 10⁴.
The node values are distinct.
root[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the tree has at most 14 levels.

Examples

Input: root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Output: [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
Explanation: Read left to right, the levels are 8; 12, 5; 1, 9, 14; 4, 2, 11. Levels 1 and 3 run backwards: [5, 12] and [11, 2, 4].

Input: root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
Output: [[1], [3, 2], [4, 5, 6, 7]]
Explanation: A full tree of three levels: the middle level flips to [3, 2] and the third runs left to right again. The two trailing -1 entries are the empty child spots of 4.

Follow-up

Can you put every value straight into its final place in its row, with no reversing and no second stack?

Solution

The levels come from an ordinary breadth-first search. The new part is direction: every other level comes out reversed. Either reverse the odd rows after you build them, or hold each level in a stack, which hands items back in the opposite order of the pushes.

Level order, then reverse every other level

Intuition

A queue processed one level per round yields each level from left to right. Number the levels from 0 at the root: the zigzag reads the odd levels from right to left, so reversing exactly those rows gives the answer.

The search visits each node once and each reversal touches each value once more, so the time is O(n).

Algorithm

Start a queue with index 0.
For each round, save the queue's length s, dequeue s indexes into a new row, and enqueue each one's existing children, left before right.
If the answer already holds an odd number of rows, reverse the row.
Append the row and continue until the queue is empty.

from collections import deque


def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        row = []
        for _ in range(len(queue)):  # exactly the nodes of the current level
            i = queue.popleft()
            row.append(root[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
        if len(levels) % 2 == 1:  # levels 1, 3, 5, ... read from right to left
            row.reverse()
        levels.append(row)
    return levels

Two stacks

Intuition

Keep the current level in a stack that pops in the direction the level is read, and push the children of each popped node onto a second stack. When the current stack empties, the second one holds the next level.

The push order makes it work. Popping left to right, push each node's left child, then its right: the rightmost node's right child goes on last, so the next level pops from its right end. Popping right to left, push right then left, and the leftmost node's left child goes on last.

Example 1: pop 8, push 12, 5. Pop 5, 12, then push 14 from 5 and 9, 1 from 12. Pop 1, 9, 14, then push 4, 2 from 9 and 11 from 14. Pop 11, 2, 4.

Each node is pushed and popped once: O(n) time, with no reversal pass.

Algorithm

Push the root's index 0 onto a stack and start reading left to right.
While the stack is not empty, pop every index into a new row, and push each popped node's existing children onto a second stack: left then right when reading left to right, right then left otherwise.
Append the row to the answer.
Make the second stack the current one, flip the direction and repeat.

def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    current = [0]  # a stack of node indexes; the root is never empty
    left_to_right = True
    while current:
        row = []
        upcoming = []  # the next level, pushed while this one pops
        while current:
            i = current.pop()
            row.append(root[i])
            # Push so that the next level pops out in its own direction.
            if left_to_right:
                children = (2 * i + 1, 2 * i + 2)
            else:
                children = (2 * i + 2, 2 * i + 1)
            for child in children:
                if child < n and root[child] != -1:
                    upcoming.append(child)
        levels.append(row)
        current = upcoming
        left_to_right = not left_to_right
    return levels

Pitfalls and edge cases

Flipping the order in which children enter a single queue. Siblings swap but parents keep their order: example 1's third level comes out as [9, 1, 14].
Counting levels from 1. Every flip lands one level off, and example 1 gives [[8], [12, 5], [14, 9, 1], [4, 2, 11]].
Using one push order on every level of the two-stack version. Example 1's third level then pops as [9, 1, 14].
Pushing children onto the stack you are still popping. They come off before the rest of their parent's level.
Sorting a row instead of reversing it. The last level of example 1 must be [11, 2, 4], which no sort produces.

Frequently asked questions3

What is the difference between zigzag and level order traversal?

They visit the same levels with the same nodes. Level order reads every level from left to right; zigzag reads every second level from right to left, starting with the level below the root. Both run in O(n) time.

Is zigzag traversal the same as spiral order traversal of a tree?

Yes, the two names describe the same walk. Some texts start the second level from the left instead of the right, which only moves the flips by one level. Here the root's level goes left to right and the next one right to left.

Can zigzag level order be done with a deque?

Yes. Keep each level in the deque in left-to-right order. On a left-to-right level, take nodes from the front and add their children, left then right, at the back. On a right-to-left level, take nodes from the back and add their children, right then left, at the front. The count you take when a round begins still marks the level.

def zigzagLevelOrder(root):
    # Write code here

Test #1

Test #2

Test #3

Argument

root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]

Expected Output

[[8], [5, 12], [1, 9, 14], [11, 2, 4]]