Binary Tree Zigzag Level Order Traversal

▶

Steps

setup

Initialize stacks and variables

Initialize two stacks: currentLevel with the root node (3), and nextLevel as empty. Set result as empty list and direction flag left_to_right as True.

💡 Setting up these stacks and flags is crucial to control the zigzag traversal order.

Line:

currentLevel = [root]
nextLevel = []
result = []
left_to_right = True

💡 The two stacks will alternate roles to process nodes level by level in zigzag order.

fill_cells

Start processing first level: pop node 3

Pop node 3 from currentLevel stack and add its value to level_vals. Mark node 3 as active.

💡 Processing nodes one by one from currentLevel stack builds the current level's values.

Line:

node = currentLevel.pop()
level_vals.append(node.val)

💡 Popping from stack processes nodes in LIFO order; here only one node at level 0.

fill_cells

Push children of node 3 to nextLevel (left to right)

Since direction is left_to_right, push left child (9) then right child (20) of node 3 onto nextLevel stack.

💡 Order of pushing children controls the zigzag pattern for the next level.

Line:

if left_to_right:
    if node.left:
        nextLevel.append(node.left)
    if node.right:
        nextLevel.append(node.right)

💡 Children are stacked so that next level processes nodes in reverse order of pushing.

fill_row

Finish first level and prepare for second level

First level done with level_vals = [3]. Append it to result. Swap currentLevel and nextLevel stacks. Reset nextLevel to empty. Toggle direction to right_to_left.

💡 Swapping stacks and toggling direction prepares for next level traversal in opposite order.

Line:

result.append(level_vals)
currentLevel, nextLevel = nextLevel, []
left_to_right = not left_to_right

💡 Alternating direction after each level creates the zigzag pattern.

fill_cells

Start processing second level: pop node 20

Pop node 20 from currentLevel stack (which now contains nodes 9 and 20). Add its value to level_vals. Mark node 20 as active.

💡 Processing nodes in currentLevel stack in LIFO order means node 20 is processed before node 9 at this level.

Line:

node = currentLevel.pop()
level_vals.append(node.val)

💡 Stack order reverses the natural left-to-right order, enabling zigzag traversal.

fill_cells

Push children of node 20 to nextLevel (right to left)

Since direction is right_to_left, push right child (7) then left child (15) of node 20 onto nextLevel stack.

💡 Reversing the push order compared to left_to_right ensures zigzag traversal on next level.

Line:

else:
    if node.right:
        nextLevel.append(node.right)
    if node.left:
        nextLevel.append(node.left)

💡 The order children are pushed controls the order they will be processed next level.

fill_cells

Pop node 9 from currentLevel stack

Pop node 9 from currentLevel stack and add its value to level_vals. Mark node 9 as active.

💡 Continue processing all nodes at current level before moving on.

Line:

node = currentLevel.pop()
level_vals.append(node.val)

💡 All nodes at a level are processed before swapping stacks and toggling direction.

fill_cells

Node 9 has no children to push

Node 9 has no left or right children, so nothing is pushed to nextLevel stack.

💡 Leaf nodes do not add any nodes to nextLevel stack.

Line:

if left_to_right:
    if node.left:
        nextLevel.append(node.left)
    if node.right:
        nextLevel.append(node.right)
else:
    if node.right:
        nextLevel.append(node.right)
    if node.left:
        nextLevel.append(node.left)

💡 Leaves do not affect next level's nodes.

fill_row

Finish second level and prepare for third level

Second level done with level_vals = [20, 9]. Append it to result. Swap currentLevel and nextLevel stacks. Reset nextLevel to empty. Toggle direction to left_to_right.

💡 Swapping stacks and toggling direction again prepares for next level traversal in opposite order.

Line:

result.append(level_vals)
currentLevel, nextLevel = nextLevel, []
left_to_right = not left_to_right

💡 Alternating direction after each level creates the zigzag pattern.

fill_cells

Start processing third level: pop node 15

Pop node 15 from currentLevel stack and add its value to level_vals. Mark node 15 as active.

💡 Processing nodes in currentLevel stack in LIFO order means node 15 is processed before node 7 at this level.

Line:

node = currentLevel.pop()
level_vals.append(node.val)

💡 Stack order reverses the natural left-to-right order, enabling zigzag traversal.

fill_cells

Node 15 has no children to push

Node 15 has no left or right children, so nothing is pushed to nextLevel stack.

💡 Leaf nodes do not add any nodes to nextLevel stack.

Line:

if left_to_right:
    if node.left:
        nextLevel.append(node.left)
    if node.right:
        nextLevel.append(node.right)
else:
    if node.right:
        nextLevel.append(node.right)
    if node.left:
        nextLevel.append(node.left)

💡 Leaves do not affect next level's nodes.

fill_cells

Pop node 7 from currentLevel stack

Pop node 7 from currentLevel stack and add its value to level_vals. Mark node 7 as active.

💡 Continue processing all nodes at current level before moving on.

Line:

node = currentLevel.pop()
level_vals.append(node.val)

💡 All nodes at a level are processed before swapping stacks and toggling direction.

fill_cells

Node 7 has no children to push

Node 7 has no left or right children, so nothing is pushed to nextLevel stack.

💡 Leaf nodes do not add any nodes to nextLevel stack.

Line:

if left_to_right:
    if node.left:
        nextLevel.append(node.left)
    if node.right:
        nextLevel.append(node.right)
else:
    if node.right:
        nextLevel.append(node.right)
    if node.left:
        nextLevel.append(node.left)

💡 Leaves do not affect next level's nodes.

fill_row

Finish third level and complete traversal

Third level done with level_vals = [15, 7]. Append it to result. currentLevel stack is now empty, so traversal ends.

💡 Appending the last level's values completes the zigzag traversal.

Line:

result.append(level_vals)
# currentLevel is empty, so exit loop
return result

💡 Traversal ends when no more nodes remain to process.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def zigzagLevelOrder(root):
    if not root:
        return []
    currentLevel = [root]  # STEP 1
    nextLevel = []        # STEP 1
    result = []           # STEP 1
    left_to_right = True  # STEP 1
    while currentLevel:    # STEP 2 loop start
        level_vals = []   # STEP 2
        while currentLevel:  # STEP 3 inner loop
            node = currentLevel.pop()  # STEP 3
            level_vals.append(node.val)  # STEP 3
            if left_to_right:  # STEP 4 decision
                if node.left:
                    nextLevel.append(node.left)  # STEP 4
                if node.right:
                    nextLevel.append(node.right)  # STEP 4
            else:
                if node.right:
                    nextLevel.append(node.right)  # STEP 4
                if node.left:
                    nextLevel.append(node.left)  # STEP 4
        result.append(level_vals)  # STEP 5
        currentLevel, nextLevel = nextLevel, []  # STEP 5
        left_to_right = not left_to_right  # STEP 5
    return result  # STEP 6

# Driver code
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    print(zigzagLevelOrder(root))

📊

Binary Tree Zigzag Level Order Traversal - Watch the Algorithm Execute, Step by Step

Watching this step-by-step execution reveals how the two stacks work together to achieve the zigzag pattern, making the traversal order and stack swapping intuitive without needing to infer from code alone.

3920157

Current node: 0

3920157

3920157

3920157

Result: [3]

Current node: 2

3920157

Result: [3]

3920157

Result: [3]

Current node: 1

3920157

Result: [3]

3920157

Result: [3]

3920157

Result: [3, 20,9]

Current node: 3

3920157

Result: [3, 20,9]

3920157

Result: [3, 20,9]

Current node: 4

3920157

Result: [3, 20,9]

3920157

Result: [3, 20,9]

3920157

Result: [3, 20,9, 15,7]

Return: [[3],[20,9],[15,7]]

Key Takeaways

✓ Using two stacks alternately allows natural reversal of node processing order, enabling zigzag traversal without complex indexing.

This insight is hard to see from code alone because the stack swapping and push order reversal are subtle and intertwined.

✓ The direction flag controls the order children are pushed onto the nextLevel stack, directly influencing the traversal order of the next level.

Seeing the actual push order and how it affects the next level clarifies why the zigzag pattern emerges.

✓ Processing all nodes at a level before swapping stacks and toggling direction ensures clean separation of levels and consistent zigzag order.

The step-by-step trace shows how the algorithm completes one level fully before moving on, which is not obvious from a quick code read.

Practice

1. You are given a binary tree and need to output the nodes grouped by their vertical columns, from leftmost column to rightmost, preserving the top-to-bottom order within each column. Which approach guarantees an optimal solution for this problem?

easy

A. Depth-first search (DFS) collecting nodes by column and sorting them by row and value afterwards

B. Greedy traversal picking nodes with minimum column index first without sorting or queue

C. Dynamic programming to compute vertical sums and then reconstruct node order

D. Breadth-first search (BFS) with column tracking using an ordered map to maintain column order and insertion order for nodes

Solution

1. Step 1: Understand problem requirements

   The problem requires grouping nodes by vertical columns and preserving top-to-bottom order within each column.

2. Step 2: Evaluate approaches

   DFS with sorting (A) works but is less efficient; greedy (B) fails to preserve order; DP (D) is unrelated. BFS with column tracking and ordered map (C) naturally preserves order and column sorting efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS with ordered map preserves vertical order and top-to-bottom traversal [OK]

Hint: BFS with ordered map preserves vertical and top-down order [OK]

Common Mistakes:

• Assuming DFS alone preserves top-to-bottom order without sorting
• Using greedy approach ignoring node order within columns

2. Consider the following Python code for N-ary tree level order traversal. Given the tree root = Node(1, [Node(3, [Node(5), Node(6)]), Node(2), Node(4)]), what is the value of res after the first iteration of the outer while loop completes?

easy

A. [[1]]

B. [[1, 3, 2, 4]]

C. [[3, 2, 4]]

D. [[5, 6]]

Solution

1. Step 1: Trace the first outer loop iteration

   Initially, current_level contains only the root node with value 1.

2. Step 2: Collect values and enqueue children

   We pop node 1, append its value to level_nodes -> [1], and enqueue its children (3, 2, 4) into next_level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After first iteration, res = [[1]] as only root level processed [OK]

Hint: First level contains only root node value [OK]

Common Mistakes:

• Confusing first level with all children nodes

3. You are given a perfect binary tree where each node has two children. The task is to connect each node's next pointer to its immediate right neighbor on the same level, or NULL if there is none. Which approach guarantees an optimal solution with O(1) extra space and O(n) time complexity?

easy

A. Use the already established next pointers to traverse each level and connect children without extra space.

B. Perform a level order traversal using a queue to connect nodes at each level.

C. Apply a dynamic programming approach to store and connect nodes level-wise.

D. Use a depth-first search recursion to connect nodes from top to bottom.

Solution

1. Step 1: Understand the problem constraints

   The tree is perfect, so every node has two children, and all leaves are at the same level.

2. Step 2: Identify the approach that uses constant extra space

   Using next pointers already set on the current level to connect the next level avoids extra data structures like queues.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses existing pointers to traverse levels [OK]

Hint: Use next pointers to traverse levels without extra space [OK]

Common Mistakes:

• Assuming BFS with queue is optimal space-wise
• Confusing DFS recursion with constant space
• Using DP which is unrelated

4. Suppose you want to modify the level order traversal to return the nodes in reverse level order (from bottom level to top). Which of the following approaches correctly achieves this without increasing time complexity beyond O(n)?

hard

A. Perform BFS but insert each level's list at the front of the result list during traversal

B. Perform normal BFS and then reverse the final list of levels before returning

C. Modify BFS to enqueue children at the front of the queue instead of the back

D. Use DFS to collect nodes by level and then reverse the collected list

Solution

1. Step 1: Understand reversing levels efficiently

   Performing normal BFS and then reversing the final list of levels is straightforward and maintains O(n) time complexity.

2. Step 2: Analyze insertion at front complexity

   Inserting each level at the front of a list during BFS can be O(n) per insertion if using a Python list, leading to O(n²) total time.

3. Step 3: Evaluate other options

   Using DFS and then reversing uses extra stack space; modifying BFS queue order breaks BFS semantics.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Reversing the final list after BFS is simple, correct, and efficient [OK]

Hint: Perform BFS normally and reverse result list to get reverse level order efficiently [OK]

Common Mistakes:

• Inserting at front of list during BFS can cause O(n²) time

5. Suppose the problem is extended so that the tree nodes can have multiple children (not just binary), and you need to check if the tree is symmetric around its center. Which modification to the BFS approach is necessary to correctly handle this case?

hard

A. Enqueue children in normal order and compare corresponding children pairs directly

B. Enqueue children in mirrored order and compare pairs from opposite ends of the children list

C. Use a recursive approach only, as BFS cannot handle multiple children

D. Check symmetry only at the root level and ignore deeper levels

Solution

1. Step 1: Understand symmetry in multi-child trees

   Symmetry means the first child on the left subtree mirrors the last child on the right subtree, second mirrors second last, etc.

2. Step 2: Modify BFS to enqueue children in mirrored order

   Enqueue children pairs from opposite ends of the children list to compare mirrored positions correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Mirrored enqueue order for multiple children preserves symmetry checks [OK]

Hint: Multi-child symmetry requires mirrored child pair comparisons [OK]

Common Mistakes:

• Enqueuing children in normal order causing false positives
• Assuming BFS cannot be adapted for multi-child trees
• Ignoring deeper levels of the tree