Vertical and Zigzag Traversal of Binary Tree

Given a binary tree. Print the nodes in vertical and zigzag manner.

<strong?vertical traversal<=”” strong=””></strong?vertical>

For example, we have binary tree below:

         1
       /   \
     2       3
   /  \    /  \
  4     5 6    7

vertical traversal will output:
4
2
1 5 6
3
7

We can clearly see that we are printing the nodes in vertical order such that a vertical line is scanning from left most node to right most node and printing all the nodes on the same vertical in a single line. How do we do it? Note that, the left most node will be printed first then its root then it’s right node. So, basically we are giving highest priority to left subtree, then root, and then lowest priority to right subtree. This gives us enough hint to solve this problem. How?

We will basically traverse the tree in pre-order (root -> left -> right) such a way that we assign one higher priority when we go left and one lower priority when we go right. Then we will basically put all the nodes with same priority value in a map. Once the traversal is done we can print the map nodes in the order of priority, sam priority nodes in the same line. For example, the following tree shows the assigned priority for each node in vertical traverse order [lower value means higher priority].

        1,0
       /   \
     2,-1    3,1
   /  \      /  \
 4,-2   5,0 6,0  7,2

map :
-2 -> {4}
-1 -> {2}
 0 -> {1, 5, 6}
 1 -> {3}
 2 -> {7}

Below is a simple implementation of this idea.

public static void verticalTrversal(BTNode root){
	int[] minmax = new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
	Map<Integer, ArrayList<BTNode>> verticals = new HashMap<Integer, ArrayList<BTNode>>();
	traverse(root, verticals, 0, minmax);
	for(int i = minmax[0]; i<=minmax[1]; i++){
		if(verticals.containsKey(i)){
			for(BTNode vnode : verticals.get(i)){
				System.out.print(vnode.key+",");
			}
			System.out.println();
		}
	}
	
}

private static void traverse(BTNode node, Map<Integer, ArrayList<BTNode>> verticals, int score, int[] minmax){
	if(!verticals.containsKey(score)){
		verticals.put(score, new ArrayList<BTNode>());
	}
	
	verticals.get(score).add(node);
	minmax[0] = Math.min(minmax[0], score);
	minmax[1] = Math.max(minmax[1], score);
	
	if(node.left != null){
		traverse(node.left, verticals, score-1, minmax);
	}
	if(node.right != null){
		traverse(node.right, verticals, score+1, minmax);
	}
}

ZigZag 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
    /  \
   15   7

print its zigzag level order traversal as:

3
20,9
15,7

If we look closely then we can notice that this is basically a level order (or horizontal) traversal where we are changing direction (left or right) at alternate level. Please read my previous post on level order traversal before reading more in this article.

So, basically we will do a level order (left to right per level) traversal but we need to print in reverse order in alternate level. We can keep a stack to save the nodes in reverse order (right to left) if we are in a even level. At the end of an even level we will print from the stack. On the other hand for odd level we just print as we traverse from left to right. Below is the implementation of this level order traversal using a queue.

public static void zigzagTraversal(BTNode root){
	Queue<BTNode> queue = new ArrayDeque<BTNode>();
	queue.offer(root);
	
	BTNode node = null;
	int count = 1;
	int level = 0;
	Stack<BTNode> reverse = new Stack<BTNode>();
	while(!queue.isEmpty()){
		node = queue.poll();
		count--;
		
		//right to left
		if((level&1) == 0){
			reverse.push(node);
		}
		else{
			System.out.print(node.key);
		}
		
		if(node.left != null){
			queue.offer(node.left);
		}
		if(node.right != null){
			queue.offer(node.right);
		}
		
		//level ended
		if(count == 0){
			if((level&1) == 0){
				while(!reverse.isEmpty()){
					System.out.print(reverse.pop().key);
				}
			}
			System.out.println();
			
			count = queue.size();
			level++;
		}
	}
}