The O(n) Club: Binary Tree Zigzag Level Order Traversal: When BFS Decides to Salsa

The O(n) Club: Binary Tree Zigzag Level Order Traversal: When BFS Decides to Salsa

⚡ TL;DR

Zigzag level order traversal means stomping your way through the tree level by level, but with a plot twist: swap direction at every new row. Don’t just flip arrays after — commit to your zig as you traverse and zag with purpose. Example Java code coming up. (No caffeine required, but recommended.)

// Java BFS using deque, alternating left/right at each level.
List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (leftToRight) level.addLast(node.val);
            else level.addFirst(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}

🧠 How Devs Usually Mess This Up

You’d think, “Just BFS, then reverse every other row at the end, right?” Wrong. That shortcut is the beginning of bugs and the end of your self-esteem—especially in gnarly, lopsided trees. Another classic: mistaking zigzag for in-order or pre-order traversal. Spoiler: zigzag is BFS with salsa steps, not DFS with regret.

🔍 What’s Actually Going On

Picture a group of robots climbing stairs: first row marches left to right, the next shuffles right to left, like a synchronized dance for the CPU amusement. Solution: on each level, as you pull nodes from the queue, decide on the spot which end to stuff their values into. BFS with commitment issues is still BFS; we’re just toggling our loyalties every level.

🛠️ PseudoCode

• Place root in a queue. Track direction with a boolean — call it leftToRight (start true).
• While your queue isn’t empty:
  • Get the number of nodes at this level (levelSize).
  • Create a shiny new LinkedList to hold this level’s values.
  • For each node:
    • If leftToRight, add value at end of LinkedList.
    • If not, add value right at the front. So bold.
    • Offer left/right children to the queue. No discrimination allowed.
  • Bask in your work by adding LinkedList to the result array.
  • Flip your boolean flag — next time, other direction!
• Return result, secure in your O(N) majesty.

💻 The Code

// TreeNode definition for the noobs
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        LinkedList<Integer> levelList = new LinkedList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode current = queue.poll();
            if (leftToRight) levelList.addLast(current.val);
            else levelList.addFirst(current.val);
            if (current.left != null) queue.offer(current.left);
            if (current.right != null) queue.offer(current.right);
        }
        result.add(levelList);
        leftToRight = !leftToRight;
    }
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• null root? Just return an empty list; don’t add existential dread to your bugs.
• Reversing after BFS? You’ll break stuff in unbalanced trees. Collect as you go, not after.
• ArrayList for every level? Good luck with insert(0, item) inside big loops. Use LinkedList if you need frequent insertions at both ends.
• Time and space: visit each node once, store every value — both O(N). No O(N^2) drama today.

🧠 Interviewer Brain-Tattoo

Just because it’s “zigzag” doesn’t mean your control flow should look like one. Commit to your direction on each step, and your code — unlike your morning plans — will actually work.