Binary Tree Zigzag Level Order Traversal

📋

Problem

Imagine you are organizing a company hierarchy chart where you want to list employees level by level, but alternate the direction of listing each level to make the chart visually engaging.

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). Input: root node of a binary tree. Output: a list of lists of integers representing node values in zigzag level order.

The number of nodes in the tree is in the range [0, 10^5].-10^9 <= Node.val <= 10^9

Edge cases: Empty tree → []Tree with only one node → [[node_value]]Tree with all nodes only on left → zigzag alternates but only one node per level

</>

IDE

def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:public List<List<Integer>> zigzagLevelOrder(TreeNode root)vector<vector<int>> zigzagLevelOrder(TreeNode* root)function zigzagLevelOrder(root)

def zigzagLevelOrder(root):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    // Write your solution here
    return {};
}

function zigzagLevelOrder(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[3],[9,20],[15,7]]Not reversing the nodes at odd levels, so level 1 is left to right instead of right to left.✅ Add reversal of the current level's node list when level index is odd: if level % 2 == 1: current_level.reverse()

Wrong: [[1],[2],[3],[4],[5]]Always traversing left to right without alternating direction, ignoring zigzag pattern.✅ Use a level counter and reverse the node list at every odd level to alternate direction.

Wrong: [[1],[2,3],[4,5,6,7]]Not reversing the nodes at odd levels, so level 1 is left to right instead of right to left.✅ Reverse the node list at odd levels before appending to result.

Wrong: Exception or incorrect output on empty inputNo base case for empty tree, causing null pointer or index errors.✅ Add base case: if root is None: return []

Wrong: [[1],[3,2],[4,5,6,7],[8,9]]Off-by-one error in level counting or reversal logic causing last level reversal to be incorrect.✅ Ensure level counter increments correctly and reversal applies only on odd levels.

✓

Test Cases

Try testing your code on empty and single-node trees to catch base case bugs.

Test with full and sparse trees to catch off-by-one and null handling bugs.

Optimize your BFS to avoid costly reversals and achieve linear time complexity.

t1_01basic

Input{"root":[3,9,20,null,null,15,7]}

Expected[[3],[20,9],[15,7]]

⏱ Performance - must finish in 2000ms

Level 0: left to right → [3]; Level 1: right to left → [20,9]; Level 2: left to right → [15,7]

💡 Think about traversing the tree level by level using a queue.

💡 Use a flag or counter to reverse the order of nodes at every alternate level.

💡 Reverse the collected nodes at odd levels before adding them to the result.

Why it failed: Output does not alternate direction per level. Fix by reversing the node list at every odd level before appending.

✓ Correct zigzag traversal with alternating directions per level.

t1_02basic

Input{"root":[1,2,3,4,null,null,5]}

Expected[[1],[3,2],[4,5]]

⏱ Performance - must finish in 2000ms

Level 0: [1]; Level 1 reversed: [3,2]; Level 2 normal: [4,5]

💡 Process nodes level by level and track the current level index.

💡 Reverse the order of nodes collected at odd levels before adding to result.

💡 Use a queue to hold nodes and reverse the list at odd levels.

Why it failed: Failed to reverse nodes at odd levels causing incorrect order. Add reversal step for odd levels.

✓ Correctly alternates traversal direction per level.

t2_01edge

Input{"root":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty tree returns empty list.

💡 Check if the root is null or empty before processing.

💡 Return an empty list immediately if no nodes exist.

💡 Add a base case to handle empty input.

Why it failed: Code crashes or returns non-empty output on empty input. Add base case: if root is None return [].

✓ Handles empty tree input correctly.

t2_02edge

Input{"root":[42]}

Expected[[42]]

⏱ Performance - must finish in 2000ms

Single node tree returns one level with that node.

💡 Test with only one node to verify base case.

💡 Ensure the code handles single-level trees without reversing.

💡 Return [[root.val]] when only one node exists.

Why it failed: Fails single node case by reversing or returning empty. Fix by returning [[root.val]] for single node.

✓ Correctly returns single node in a list.

t2_03edge

Input{"root":[1,2,null,3,null,4,null,5]}

Expected[[1],[2],[3],[4],[5]]

⏱ Performance - must finish in 2000ms

Tree with nodes only on left side; each level has one node, zigzag has no visible effect.

💡 Test trees skewed to one side to check level handling.

💡 Zigzag reversal on single element levels should not change output.

💡 Ensure reversal logic does not break single-node levels.

Why it failed: Reversal logic breaks single-node levels or causes errors. Fix by reversing only when level size > 1.

✓ Handles skewed left tree with correct zigzag output.

t3_01corner

Input{"root":[1,2,3,4,5,6,7]}

Expected[[1],[3,2],[4,5,6,7]]

⏱ Performance - must finish in 2000ms

Full binary tree to test correct zigzag order and no greedy mistakes.

💡 Beware of greedy approaches that do not alternate direction properly.

💡 Use a level counter to decide when to reverse the level nodes.

💡 Reverse the collected nodes only at odd levels, not based on node values.

Why it failed: Greedy approach fails by reversing based on node values or partial conditions. Fix by reversing strictly on odd levels.

✓ Correctly alternates direction level by level.

t3_02corner

Input{"root":[1,2,3,null,4,null,5]}

Expected[[1],[3,2],[4,5]]

⏱ Performance - must finish in 2000ms

Sparse tree tests correct handling of null children and zigzag order.

💡 Ensure null children do not get added to the queue.

💡 Check that only existing nodes are processed per level.

💡 Reverse the collected nodes at odd levels after filtering nulls.

Why it failed: Including null nodes in queue causes wrong output or errors. Fix by skipping null children when enqueueing.

✓ Handles sparse trees correctly with proper zigzag order.

t3_03corner

Input{"root":[1,2,3,4,5,6,7,8,null,null,9]}

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

⏱ Performance - must finish in 2000ms

Test with last level partially filled and zigzag reversal on last level.

💡 Check that reversal applies correctly even on last level with partial nodes.

💡 Use a deque or list reversal after collecting nodes per level.

💡 Ensure no off-by-one errors in level counting.

Why it failed: Off-by-one error causes wrong reversal or missing nodes on last level. Fix by incrementing level counter correctly and reversing at odd levels.

✓ Correctly handles partial last level with zigzag order.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large complete binary tree with 100 nodes; O(n) BFS traversal must complete within 2 seconds.

💡 Use BFS with a queue or deque for O(n) traversal.

💡 Avoid reversing lists by using deque or two stacks for zigzag order.

💡 Optimize by appending nodes in correct order without extra reversal.

Why it failed: Algorithm exceeds time limit due to inefficient reversal or repeated traversals. Fix by using deque or two stacks to achieve O(n) time.

✓ Algorithm runs in O(n) time and passes performance constraints.

Practice

1. Identify the bug in the following code snippet for the right side view of a binary tree:

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightside):
            rightside.append(node.val)
        dfs(node.left, depth + 1)  # Line X
        dfs(node.right, depth + 1) # Line Y
    dfs(root, 0)
    return rightside

Which line contains the bug causing incorrect right side view?

medium

A. Line with 'if depth == len(rightside): rightside.append(node.val)'

B. Line X: 'dfs(node.left, depth + 1)'

C. Line Y: 'dfs(node.right, depth + 1)'

D. Line with 'if not node: return'

Solution

1. Step 1: Understand traversal order

   The code visits left child before right child, so left nodes are appended first at each depth.

2. Step 2: Why this causes bug

   Visiting left first causes left nodes to be recorded as visible, overwriting right nodes that should be visible from the right side.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping left and right child calls fixes the bug [OK]

Hint: Right-first DFS needed to capture rightmost nodes [OK]

Common Mistakes:

• Visiting left child before right in DFS causes wrong nodes appended
• Appending nodes without checking depth length
• Not handling null nodes properly

2. What is the time complexity of the BFS-based solution for finding the largest value in each tree row, assuming n is the number of nodes and w is the maximum width of the tree?

medium

A. O(n * w) because for each node we scan all nodes at its level

B. O(n log w) due to maintaining a max heap per level

C. O(n) because each node is enqueued and dequeued exactly once

D. O(w) since we only track the maximum per level

Solution

1. Step 1: Identify that each node is processed once

   Each node is enqueued once and dequeued once, so total operations proportional to n.

2. Step 2: Confirm no nested loops over nodes beyond level size

   Inner loop runs for each level's nodes, summing to n overall, so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Each node visited once -> O(n) time [OK]

Hint: Each node processed once in BFS -> O(n) time [OK]

Common Mistakes:

• Confusing level width w as multiplicative factor
• Assuming sorting or heap operations per level
• Ignoring that inner loop sums to n over all levels

3. Examine the following buggy BFS code for checking tree symmetry. Which line contains the subtle bug that causes incorrect results on asymmetric trees?

medium

A. Line checking if t1.val != t2.val

B. Line appending t1.right and t2.right to the queue

C. Line appending t1.left and t2.left to the queue

D. Line checking if not t1 or not t2

Solution

1. Step 1: Identify enqueue order for mirrored nodes

   Mirrored nodes must be enqueued as (t1.left, t2.right) and (t1.right, t2.left) to compare symmetric positions.

2. Step 2: Locate incorrect enqueue causing wrong pairs

   The code enqueues (t1.left, t2.left) and (t1.right, t2.right), which compares left subtree to left subtree, breaking symmetry checks.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incorrect enqueue order causes false positives on asymmetric trees [OK]

Hint: Mirrored enqueue order must be left-right pairs [OK]

Common Mistakes:

• Swapping mirrored enqueue order
• Missing null checks causing exceptions
• Incorrect value comparisons

4. Suppose the problem changes: instead of finding the largest value per tree row, you must find the top 2 largest values per row. Which modification to the BFS approach correctly solves this with optimal time complexity?

hard

A. Keep track of the two largest values per level by updating two variables during BFS traversal of each level.

B. Store all node values per level in a list, then sort the list to pick top 2 after BFS completes.

C. Run BFS twice: first to find max, second to find second max by ignoring max nodes.

D. Use DFS with level tracking and maintain a max-heap per level to extract top 2 values.

Solution

1. Step 1: Understand BFS level order traversal processes nodes per level

   We can track two largest values inline by comparing each node's value to current top two during the level loop.

2. Step 2: Avoid sorting or multiple traversals for efficiency

   Sorting all values or multiple BFS runs increase time complexity unnecessarily; inline tracking keeps O(n) time.

3. Step 3: Confirm DFS with heaps adds extra space and complexity

   DFS with heaps is more complex and less efficient than inline BFS tracking.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Inline top-2 tracking per level -> O(n) time, O(w) space [OK]

Hint: Track top 2 inline during BFS to avoid sorting [OK]

Common Mistakes:

• Sorting all values per level causing O(n log n) time
• Multiple BFS passes increasing runtime
• Using DFS with heaps unnecessarily complicates solution

5. Suppose the problem changes: instead of finding the minimum depth to any leaf, you must find the minimum depth to a leaf node with a specific target value. Which modification to the BFS approach is correct?

hard

A. Continue BFS until the first leaf is found, then check if its value matches target; if not, continue BFS

B. Use DFS to explore all paths and return the minimum depth of leaves matching the target value

C. Modify BFS to enqueue only nodes whose values are less than or equal to the target value

D. Stop BFS at the first node with the target value, regardless of whether it is a leaf

Solution

1. Step 1: Understand the new requirement

   We want the minimum depth to a leaf node with a specific value, not just any leaf.

2. Step 2: Modify BFS to check leaf value before returning

   BFS should stop only when it finds a leaf node whose value matches the target; otherwise, continue searching.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS guarantees shortest path; checking leaf value before stopping is correct [OK]

Hint: BFS with conditional leaf check for target value [OK]

Common Mistakes:

• Stopping at first leaf regardless of value
• Pruning BFS incorrectly by node values
• Switching to DFS losing BFS optimality