LeetCode 103: Binary Tree Zigzag Level Order Traversal Solution

Master LeetCode problem 103 (Binary Tree Zigzag Level Order Traversal), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

103. Binary Tree Zigzag Level Order Traversal

Medium

Tree Breadth-First Search Binary Tree

Problem Explanation

Explanation

To solve this problem, we can perform a level order traversal of the binary tree while keeping track of the level of each node. We will use a queue to perform the traversal. At each level, we will alternate the direction in which we traverse the nodes.

We start by creating a queue and adding the root node to it.
While the queue is not empty, we iterate through the nodes at the current level.
For each node, we add its value to the current level list.
If the current level is odd, we add the children nodes to the queue in the order of right child followed by left child.
If the current level is even, we add the children nodes to the queue in the order of left child followed by right child.
We repeat this process until all levels are traversed.
Finally, we return the list of lists containing the zigzag level order traversal of the binary tree nodes.

Time complexity: O(N) where N is the number of nodes in the binary tree. Space complexity: O(N) for the queue and the output list.

Solution Code

import java.util.*;

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 zigzag = false;

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

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                if (zigzag) {
                    level.add(0, node.val);
                } else {
                    level.add(node.val);
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(level);
            zigzag = !zigzag;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 103 (Binary Tree Zigzag Level Order Traversal)?

This page provides optimized solutions for LeetCode problem 103 (Binary Tree Zigzag Level Order Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 103 (Binary Tree Zigzag Level Order Traversal)?

The time complexity for LeetCode 103 (Binary Tree Zigzag Level Order Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 103 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 103 in Java, C++, or Python.

Back to LeetCode Solutions