Last updated on January 5th, 2025 at 01:13 am

Here, we see a Binary Tree Zigzag Level Order Traversal LeetCode Solution. This Leetcode problem is solved in many programming languages, such as C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Breadth-First Search, Stack, Tree

Companies

Bloomberg, LinkedIn, Microsoft

Level of Question

Medium

Binary Tree Zigzag Level Order Traversal LeetCode Solution

1. 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 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: []

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Tree Breadth-First Search (BFS). This pattern is used to traverse a tree level by level, and in this case, it is modified to handle the zigzag traversal by alternating the order of elements at each level.

3. Code Implementation in Different Languages

3.1 Binary Tree Zigzag Level Order Traversal C++

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        if (root == NULL) {
            return vector<vector<int> > ();
        }
        vector<vector<int> > result;
        queue<TreeNode*> nodesQueue;
        nodesQueue.push(root);
        bool leftToRight = true;
        while ( !nodesQueue.empty()) {
            int size = nodesQueue.size();
            vector<int> row(size);
            for (int i = 0; i < size; i++) {
                TreeNode* node = nodesQueue.front();
                nodesQueue.pop();
                int index = (leftToRight) ? i : (size - 1 - i);
                row[index] = node->val;
                if (node->left) {
                    nodesQueue.push(node->left);
                }
                if (node->right) {
                    nodesQueue.push(node->right);
                }
            }
            leftToRight = !leftToRight;
            result.push_back(row);
        }
        return result;
    }
};

3.2 Binary Tree Zigzag Level Order Traversal Java

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
    {
        List<List<Integer>> sol = new ArrayList<>();
        travel(root, sol, 0);
        return sol;
    }
    
    private void travel(TreeNode curr, List<List<Integer>> sol, int level)
    {
        if(curr == null) return;
        if(sol.size() <= level)
        {
            List<Integer> newLevel = new LinkedList<>();
            sol.add(newLevel);
        }
        List<Integer> collection  = sol.get(level);
        if(level % 2 == 0) collection.add(curr.val);
        else collection.add(0, curr.val);
        travel(curr.left, sol, level + 1);
        travel(curr.right, sol, level + 1);
    }
}

3.3 Binary Tree Zigzag Level Order Traversal JavaScript

var zigzagLevelOrder = function(root) {
    if(!root) return [];
    let queue = [root];
    let output = [];
    let deep = 0;
    while(queue.length > 0){
        const size = queue.length;
        const level = [];
        for(let i=0; i< size; i++){
        const node = queue.shift();
        if(deep % 2 == 0) level.push(node.val);
        else level.unshift(node.val);
        if(node.left) queue.push(node.left)
        if(node.right) queue.push(node.right)
        }
        output.push(level)
        deep++;
    }
    return output
};

3.4 Binary Tree Zigzag Level Order Traversal Python

class Solution(object):
    def zigzagLevelOrder(self, root):
	if not root: return []
	queue = collections.deque([root])
	res = []
	even_level = False
	while queue:
		n = len(queue)
		level = []
		for _ in range(n):
			node = queue.popleft()
			level.append(node.val)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		if even_level:
			res.append(level[::-1])
		else:
			res.append(level)
		even_level = not even_level
	return res

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)

All implementations use the Tree Breadth-First Search (BFS) pattern to traverse the tree level by level. The zigzag order is achieved by either reversing the level list or inserting elements at the beginning of the list for alternate levels. The time complexity is O(N) for all implementations, and the space complexity is O(N) due to the storage requirements for the queue and result list.