Leetcode 103. Binary Tree Zigzag Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

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).

DFS Recursive Approach 1


class Solution {
    protected void DFS(TreeNode node, int level, List> results) {
        if (level >= results.size()) {
            LinkedList newLevel = new LinkedList();
            newLevel.add(node.val);
            results.add(newLevel);
        } else {
            if (level % 2 == 0)
                results.get(level).add(node.val);
            else
                results.get(level).add(0, node.val);
        }

        if (node.left != null)
            DFS(node.left, level + 1, results);
        if (node.right != null)
            DFS(node.right, level + 1, results);
    }

    public List> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList>();
        }
        List> results = new ArrayList>();
        DFS(root, 0, results);
        return results;
    }
}

Time and Space Complexity: O(n)

BFS Iterative Approach 2


class Solution {
    public List> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList>();
        }

        List> results = new ArrayList>();

        // add the root element with a delimiter to kick off the BFS loop
        LinkedList nQueue = new LinkedList();
        nQueue.addLast(root);
        nQueue.addLast(null);

        LinkedList levelList = new LinkedList();
        boolean isLeft = true;

        while (nQueue.size() > 0) {
            TreeNode currNode = nQueue.pollFirst();
            if (currNode != null) {
                if (isLeft)
                    levelList.addLast(currNode.val);
                else
                    levelList.addFirst(currNode.val);

                if (currNode.left != null)
                    nQueue.addLast(currNode.left);
                if (currNode.right != null)
                    nQueue.addLast(currNode.right);

            } else {
                // we finish the scan of one level
                results.add(levelList);
                levelList = new LinkedList();
                
                // prepare for the next level
                if (nQueue.size() > 0)
                    nQueue.addLast(null);
                isLeft = !isLeft;
            }
        }
        return results;
    }
}

Time Complexity: and Space Complexity:

See Video lecture

Leetcode 103. Binary Tree Zigzag Level Order Traversal

Introduction

Binary Tree Zigzag Level Order Traversal is a variation of the traditional level order traversal, where the tree is traversed in a zigzag or alternating pattern. Instead of processing nodes level by level from left to right, this algorithm alternates the traversal direction for each level. This traversal technique is especially useful for scenarios that require visual representation or alternate processing of hierarchical data.

Problem Statement

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).

Example

Consider the following binary tree:

The zigzag level order traversal output is:

Approach

The solution involves performing a level order traversal using a queue and adding nodes' values to the result list in alternating order for each level.

Steps to Solve

Initialize a queue for breadth-first traversal and add the root node.
Use a boolean flag leftToRight to track the traversal direction.
For each level, use a loop to process all nodes at that level, storing their values in a temporary list.
Reverse the temporary list if the flag leftToRight is false.
Toggle the flag at the end of each level.
Store the processed level's values in the result list.

Implementation in Java

Below is the Java implementation of the Binary Tree Zigzag Level Order Traversal:


import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public List> zigzagLevelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue queue = new LinkedList<>();
        queue.add(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                if (leftToRight) {
                    currentLevel.add(currentNode.val);
                } else {
                    currentLevel.add(0, currentNode.val); // Add to the beginning for reverse order
                }

                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }

            result.add(currentLevel);
            leftToRight = !leftToRight; // Toggle the direction
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is processed once.
Space Complexity: O(n), for the queue and the result list.

Recursive Approach

The recursive approach uses depth-first traversal to populate the values for each level, and alternates the direction by reversing values at odd levels.

Implementation


import java.util.*;

class Solution {
    public List> zigzagLevelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        traverse(root, 0, result);
        return result;
    }

    private void traverse(TreeNode node, int level, List> result) {
        if (node == null) {
            return;
        }

        if (level >= result.size()) {
            result.add(new ArrayList<>());
        }

        if (level % 2 == 0) {
            result.get(level).add(node.val); // Left to right
        } else {
            result.get(level).add(0, node.val); // Right to left
        }

        traverse(node.left, level + 1, result);
        traverse(node.right, level + 1, result);
    }
}

Applications

Zigzag level order traversal is useful in various applications:

UI Design: Organizing hierarchical data with alternating emphasis for levels.
Tree Representation: For visual representation of binary trees in a zigzag format.
Data Processing: Alternate processing of hierarchical data structures like decision trees.

Common Mistakes

Not toggling the leftToRight flag, leading to incorrect traversal directions.
Reversing the entire result instead of reversing values within each level.
Failing to initialize the result list or the temporary level list.

Edge Cases

An empty tree (return an empty list).
A tree with only one node (return a list with one level).
A tree where all nodes have only one child (unbalanced tree).

Sample Output

Consider the binary tree:

The zigzag level order traversal output is:

Conclusion

Binary Tree Zigzag Level Order Traversal is an advanced tree traversal problem that alternates the traversal direction for each level. It enhances understanding of breadth-first search and list manipulation techniques. By practicing problems like this, you improve your problem-solving and algorithmic skills, which are vital for coding interviews and real-world applications.