ZigZag Tree Traversal in JavaScript (Time Complexity: O(n))

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Example:

Input: root = [3, 9, 20, null, null, 15, 7]
    3
   / \
  9  20
    /  \
   15   7

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

Understanding the Problem

The core challenge of this problem is to traverse the binary tree in a zigzag manner. This means that for each level of the tree, we alternate the direction of traversal. The first level is traversed from left to right, the second level from right to left, the third level from left to right, and so on.

This type of traversal is significant in scenarios where the order of processing nodes alternates, such as in certain search algorithms or visual representations of tree structures.

Potential pitfalls include not correctly alternating the traversal direction or not handling null nodes properly.

Approach

To solve this problem, we can use a breadth-first search (BFS) approach with a queue to keep track of nodes at each level. We will also use a flag to alternate the direction of traversal for each level.

Here is a step-by-step approach:

Initialize a queue with the root node and a flag to indicate the direction of traversal.
While the queue is not empty, process each level of the tree.
For each level, use a temporary list to store the node values.
If the flag indicates left-to-right traversal, append node values to the temporary list. If it indicates right-to-left traversal, prepend node values to the temporary list.
After processing each level, add the temporary list to the result list and toggle the flag.

Algorithm

Here is a detailed breakdown of the algorithm:

Initialize a queue with the root node and a flag set to true (indicating left-to-right traversal).
While the queue is not empty:
- Initialize an empty list for the current level.
- Get the number of nodes at the current level.
- For each node at the current level:
  - Dequeue the node from the queue.
  - If the flag is true, append the node's value to the current level list.
  - If the flag is false, prepend the node's value to the current level list.
  - Enqueue the node's children (if any) to the queue.
- Add the current level list to the result list.
- Toggle the flag.

Code Implementation


// Definition for a binary tree node.
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

function zigzagLevelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    let leftToRight = true;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            // Add the node's value to the current level based on the traversal direction
            if (leftToRight) {
                currentLevel.push(node.val);
            } else {
                currentLevel.unshift(node.val);
            }
            
            // Enqueue the children of the current node
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        // Add the current level to the result
        result.push(currentLevel);
        
        // Toggle the traversal direction
        leftToRight = !leftToRight;
    }
    
    return result;
}

Complexity Analysis

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

The space complexity is also O(n) due to the queue used for BFS, which in the worst case can hold all the nodes at the deepest level of the tree.

Edge Cases

Some potential edge cases include:

An empty tree (root is null). The expected output is an empty list.
A tree with only one node. The expected output is a list with one sublist containing the single node's value.
A tree with multiple levels but some nodes having only one child. The algorithm should handle null children properly.

Testing

To test the solution comprehensively, consider the following test cases:

An empty tree: zigzagLevelOrder(null) should return [].
A tree with one node: zigzagLevelOrder(new TreeNode(1)) should return [[1]].
A tree with multiple levels: Use the example provided in the problem statement.

Using a testing framework like Jest can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, it is helpful to:

Break down the problem into smaller, manageable parts.
Use diagrams to visualize the tree structure and traversal process.
Consider edge cases and how the algorithm should handle them.
Practice similar problems to strengthen your understanding of tree traversal algorithms.

Conclusion

In this blog post, we discussed the zigzag level order traversal of a binary tree. We explored the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills and improving your knowledge of tree traversal algorithms.

We encourage you to practice and explore further to deepen your understanding.

Additional Resources

For further reading and practice, consider the following resources: