Zig Zag Traversal of Binary Tree

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

The LeetCode problem "Binary Tree Zigzag Level Order Traversal" requires us to traverse a binary tree in a zigzag manner. In this problem, we are tasked with outputting the node values of a given binary tree level by level, but with a twist: we alternate the direction of traversal at each level.

Understanding the Problem

Given a binary tree, our goal is to perform a level order traversal, but instead of visiting each level from left to right as is done in a standard level order traversal, we visit levels alternately from left to right and right to left. This pattern resembles a zigzag or serpentine path, which is why it is commonly referred to as a "zigzag level order traversal."

For example, consider the following binary tree:

        1
       / \
      2   3
     / \   \
    4   5   6

The zigzag level order traversal of this tree would be: [[1], [3, 2], [4, 5, 6]].

Key DSA Concepts and Theory

Binary Tree

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is a fundamental structure in computer science, facilitating fast and efficient data management and retrieval operations, especially in algorithms.

Level Order Traversal

Level order traversal is a method of traversing a tree level by level, starting from the root and proceeding downwards. A common approach to achieve this is using a queue, which facilitates linear traversal of nodes.

Queue

A queue is a First-In-First-Out (FIFO) data structure. It is ideal for breadth-first traversal of trees, as it naturally accommodates the order of nodes per level.

Solution Approach

To solve the problem, we'll utilize level order traversal with a twist to alternate the direction of node processing at each level. This can be managed using a queue to keep track of nodes and a flag to indicate the direction of traversal.

Step-by-Step Solution

  1. Initialize Data Structures:

    • Use a queue to facilitate level order traversal.
    • Create a bool flag to keep track of the current traversal direction (left to right or right to left).
    • Store the result in a list of lists.

  2. Traverse the Tree:

    • Start by enqueuing the root node.
    • Process nodes level by level:
      1. For each level, use a list to hold node values in the current level.
      2. If the flag indicates left to right, append node values directly; otherwise, insert them at the beginning of the list.
      3. Enqueue the left and right children of each node.
      4. After processing each level, toggle the direction flag.

  3. Code Implementation:

C++ Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    bool leftToRight = true;
    
    while (!nodeQueue.empty()) {
        int size = nodeQueue.size();
        vector<int> level(size);
        
        for (int i = 0; i < size; ++i) {
            TreeNode* node = nodeQueue.front();
            nodeQueue.pop();
            
            // Find position to fill node's value
            int index = leftToRight ? i : (size - 1 - i);
            
            level[index] = node->val;
            if (node->left) nodeQueue.push(node->left);
            if (node->right) nodeQueue.push(node->right);
        }
        
        // Toggle the direction
        leftToRight = !leftToRight;
        result.push_back(level);
    }
    
    return result;
}

Java Code

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    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 size = queue.size();
            List<Integer> level = new ArrayList<>(size);
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                
                if (leftToRight) {
                    level.add(node.val);
                } else {
                    level.add(0, node.val);
                }
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            leftToRight = !leftToRight;
            result.add(level);
        }
        
        return result;
    }
}

Time and Space Complexity Analysis

Time Complexity:

Both C++ and Java implementations traverse each node precisely once, leading to an overall time complexity of O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity is also O(n), as both solutions may store an entire level of the tree in the queue and resultant array lists.

Common Mistakes to Avoid

  1. Ignoring Tree Structure:

    • Ensure both left and right children are enqueued appropriately.

  2. Mismanaging Traversal Direction:

    • Properly toggle the direction flag to prevent incorrect order insertion.

Similar Problems on LeetCode

  • Binary Tree Level Order Traversal (Question 102)
  • Binary Tree Level Order Traversal II (Question 107)
  • Binary Tree Right Side View (Question 199)

Additional Resources and References

Understanding the fundamentals of binary tree structures and manipulation is crucial for solving not only this problem but a wide range of algorithmic challenges. Mastery of these concepts can be enhanced by actively solving various tree-related problems like the ones listed above.