Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

Return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

The Following Figure is explaining the zigzag level order traversal.

Binary Tree Ziz-Zac Level Order Traversal

This problem can be solved easily using Binary Tree Level Order Traversal and Array manipulation. Following is the approach:

1. Perform Level Order Traversal of the Binary Tree.
2. We would also need a variable to keep track of the current level.
  2.1 The current level can be an Odd Level or an Even Level.
  2.2 For the odd levels traverse the nodes from left to right.
  2.3 For the even levels traverse the nodes from right to left.

Following is the Java implementation:

import java.util.*;

public class ZigZagTraversal {

    public List <List<Integer>> zigzagLevelOrder(TreeNode root) {
        List <List<Integer>> nodeList = new ArrayList<>();
        if (root == null) return nodeList;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int no_of_nodes = queue.size();
            Integer[] placeHolder = new Integer[no_of_nodes];
            boolean even = (level + 1) % 2 == 0 ? true : false;
            int index = 0;
            for (int i = 0; i < no_of_nodes; i++) {
                if (even && i == 0) {
                    index = (no_of_nodes - 1);
                }
                TreeNode node = queue.remove();
                placeHolder[index] = node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                index = even ? (index - 1) : (index + 1);
            }
            nodeList.add(Arrays.asList(placeHolder));
            level++;
        }
        return nodeList;
    }
}

Time Complexity: O(n)

Categories: Binary Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s