Binary Tree Zigzag Level Order Traversal

MEDIUM

Description

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 1:

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

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Approaches

Checkout 3 different approaches to solve Binary Tree Zigzag Level Order Traversal. Click on different approaches to view the approach and algorithm in detail.

BFS with List Reversal

This approach builds upon the standard BFS level-order traversal. We traverse the tree level by level using a queue. For each level, we store the node values in a temporary list. A flag or a level counter is used to determine the traversal direction. If the current level needs to be traversed from right to left, we simply reverse the temporary list before adding it to our final result.

Algorithm

Initialize an empty list result to store the final zigzag traversal.
If the root is null, return the empty result.
Initialize a queue (e.g., LinkedList) and add the root to it.
Initialize a boolean flag leftToRight to true.
While the queue is not empty:
- Get the number of nodes in the current level, levelSize.
- Create a new list currentLevel to store the values for this level.
- Loop levelSize times:
  - Dequeue a node.
  - Add its value to currentLevel.
  - Enqueue its left child if it's not null.
  - Enqueue its right child if it's not null.
- If leftToRight is false, reverse the currentLevel list.
- Add currentLevel to the result list.
- Flip the leftToRight flag for the next level.
Return the result.

This method is a direct extension of the standard Breadth-First Search (BFS) algorithm for level-order traversal. The main idea is to perform a regular level-order traversal and collect all nodes at a given level. After a level is fully processed, we decide whether to add it to the result as is (for left-to-right levels) or to reverse it first (for right-to-left levels). A boolean flag, toggled at the end of each level's processing, keeps track of the required order.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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 levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (!leftToRight) {
                Collections.reverse(currentLevel);
            }
            result.add(currentLevel);
            leftToRight = !leftToRight;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N)Space Complexity: O(W)

Pros and Cons

Pros:

Easy to understand as it's a small modification of the standard level-order traversal.
The logic is straightforward and simple to implement.

Cons:

The explicit reversal step (Collections.reverse) adds a performance overhead compared to more optimized solutions, as it requires an extra pass over the nodes of every other level.

Code Solutions

Checking out 4 solutions in different languages for Binary Tree Zigzag Level Order Traversal. Click on different languages to view the code.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); boolean left = true ; while (! q . isEmpty ()) { List < Integer > t = new ArrayList <>(); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); t . add ( node . val ); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } if (! left ) { Collections . reverse ( t ); } ans . add ( t ); left = ! left ; } return ans ; } } ////// public class Binary_Tree_Zigzag_Level_Order_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // count as level marker class Solution { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> result = new ArrayList <>(); if ( root == null ) { return result ; } boolean isLeftToRight = true ; Queue < TreeNode > q = new LinkedList <>(); q . offer ( root ); int currentLevelCount = 1 ; int nextLevelCount = 0 ; List < Integer > one = new ArrayList <>(); while (! q . isEmpty ()) { TreeNode current = q . poll (); currentLevelCount --; if ( isLeftToRight ) { one . add ( current . val ); } else { one . add ( 0 , current . val ); } if ( current . left != null ) { q . offer ( current . left ); nextLevelCount ++; } if ( current . right != null ) { q . offer ( current . right ); nextLevelCount ++; } if ( currentLevelCount == 0 ) { currentLevelCount = nextLevelCount ; nextLevelCount = 0 ; result . add ( one ); one = new ArrayList <>(); isLeftToRight = ! isLeftToRight ; } } return result ; } } public class Solution_nullAsMarker { public List < List < Integer >> zigzagLevelOrder ( TreeNode root ) { List < List < Integer >> list = new ArrayList < List < Integer >>(); if ( root == null ) { return list ; } Queue < TreeNode > q = new LinkedList <>(); q . offer ( root ); q . offer ( null ); // @note: use null as marker for end of level boolean direction = true ; // true: left=>right, false: right=>left List < Integer > oneLevel = new ArrayList <>(); while (! q . isEmpty ()) { TreeNode current = q . poll (); if ( current == null ) { List < Integer > copy = new ArrayList <>( oneLevel ); list . add ( copy ); // clean after one level recorded oneLevel . clear (); // @memorize: this api direction = ! direction ; // @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping // sk.offer(null); // add marker if (! q . isEmpty ()) { q . offer ( null ); // add marker } continue ; } if ( direction ) { oneLevel . add ( current . val ); } else { oneLevel . add ( 0 , current . val ); } // @note:@memorize: since using null as marker, then must avoid adding null when children are null // sk.offer(current.left); // sk.offer(current.right); if ( current . left != null ) { q . offer ( current . left ); } if ( current . right != null ) { q . offer ( current . right ); } } return list ; } } }

Video Solution

Watch the video walkthrough for Binary Tree Zigzag Level Order Traversal

Algorithms:

Breadth-First Search

Data Structures:

TreeBinary Tree

Companies:

Adobe |Bloomberg |ByteDance |Flipkart |