Printing a Binary Tree in Zig Zag Level Order

Printing a Binary Tree in Zig Zag Level Order

Problem:
Given a binary tree, print out the tree in zig zag level order (ie, from left to right, then right to left for the next level and so on). Output a newline after the end of each level.

3
/ \
9 20
/ \
15 7
For example, the zig zag level order output of the tree above is:

3
20 9
15 7

Solution:

This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level’s order (whether it is left.right or right.left).

You pop from stack currentLevel and print the node’s value. Whenever the current level’s order is from left.right, you push the node’s left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level’s order is from right.left, you would push the node’s right child first, then its left child. Finally, don’t forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

void printZigZagLevelOrder(BTNode T) {   stack<BTNode> currentLevel, nextLevel;   bool leftToRight = true;   currentLevel.push(root);   while (!currentLevel.empty()) {     BTNode currNode = currentLevel.pop();        if (currNode != null) {       system.out.print(currNode.element + " ");       if (leftToRight) {         nextLevel.push(currNode.left);         nextLevel.push(currNode.right);       } else {         nextLevel.push(currNode.right);         nextLevel.push(currNode.left);       }     }     if (currentLevel.empty()) {       system.out.println("");       leftToRight = !leftToRight;       swap(currentLevel, nextLevel);     }   } }

Variation 2:

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

 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean zigzag = false;
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                if (zigzag) {
                    level.add(0, temp.val);
                }
                else {
                    level.add(temp.val);
                }
                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
            }
            result.add(level);
            zigzag = !zigzag;
        }
        return result;
    }