Binary Tree Zigzag Level Order Traversal

Chetan DattaChetan Datta
2 min read

Problem

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

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

Solution

Better Solution

Perform a BFS traversal and reverse each array based on the reversal flag.

Time - O(n)

Space -O(n)

class Solution {
    private void reverse(List<Integer> arr){
        int n = arr.size();
        for(int i=0; i<n/2; i++){
            //swap i,n-i-1
            int j = n-i-1;
            int temp = arr.get(i);
            arr.set(i, arr.get(j));
            arr.set(j, temp);
        }
    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> zigZagList = new ArrayList<>();
        if(root==null) return zigZagList;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        boolean reverseFlag = false;
        while(!queue.isEmpty()){
            List<Integer> levelOrder = new ArrayList<>();
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode node = queue.poll();
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
                levelOrder.add(node.val);
            }
            if(reverseFlag) reverse(levelOrder);
            reverseFlag = !reverseFlag;
            zigZagList.add(levelOrder);
        }

        return zigZagList;
    }
}

Optimal Solution

Perform BFS and add the level order elements to the list based on the reversal flag.

Time - O(n)

Space -O(n)

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> zigZagList = new ArrayList<>();
        if(root==null) return zigZagList;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        boolean reverseFlag = false;
        while(!queue.isEmpty()){
            List<Integer> levelOrder = new ArrayList<>();
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode node = queue.poll();
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
                int index = reverseFlag ? 0 : levelOrder.size();
                levelOrder.add(index,node.val);
            }
            reverseFlag = !reverseFlag;
            zigZagList.add(levelOrder);
        }

        return zigZagList;
    }
}
0
Subscribe to my newsletter

Read articles from Chetan Datta directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

Chetan Datta
Chetan Datta

I'm someone deeply engrossed in the world of software developement, and I find joy in sharing my thoughts and insights on various topics. You can explore my exclusive content here, where I meticulously document all things tech-related that spark my curiosity. Stay connected for my latest discoveries and observations.