Binary Tree traversal - vertically and horizontally

Binary tree traversals are one of my favorite coding problems. They can follow into two categories: travel the tree horizontally level by level; or travel the tree vertically level by level.

For example, we have binary tree below:
     1
 2     3
4 5 6  7

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

a variance of above is zig-zag traveral, which generate the below:
1
2 3
7 6 5 4

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

Here is the code:

/*
     * vertical traversal of binary tree
     */
    public static void verticalTraversal(Node root){
        Map<Integer, List<Node>> store = new HashMap<Integer, List<Node>>();
        verticalTraversalHelper(root, 0, store);
        int min=Integer.MAX_VALUE, max=Integer.MIN_VALUE;
        for(int k : store.keySet()){
            if(min>k)
                min = k;
            if(max<k)
                max = k;
        }
       
        for(int vLevel=min; vLevel<=max; vLevel++){
            for(Node n: store.get(vLevel)){
                System.out.print(n.data+" ");
            }
            System.out.println();
        }
    }
   
    private static void verticalTraversalHelper(Node node, int vLevel, Map<Integer, List<Node>> store){
        if(node==null)
            return;
        if(!store.containsKey(vLevel))
            store.put(vLevel, new ArrayList<Node>());
        store.get(vLevel).add(node);
       
        verticalTraversalHelper(node.left, vLevel--, store);
        verticalTraversalHelper(node.right, vLevel++, store);
       
    }
   
    /*
     * horizontally zig-zag traversal of tree
     * using 2 stacks
     */
    public static void zigZag(Node root){
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(root);
       
        int level = 0;
        while(!s1.isEmpty()){
            while(!s1.isEmpty()){
            Node  cur = s1.pop();
            if(level%2==0){
                if(cur.left!=null)
                    s2.push(cur.left);
                if(cur.right!=null)
                    s2.push(cur.right);
            }else{
                if(cur.right!=null)
                    s2.push(cur.right);
                if(cur.left!=null)
                    s2.push(cur.left);
            }
            }
           
            level++;
            s1 = s2;
            s2 = new Stack<Node>();
        }
    }
   
    /*
     * level traversal of tree using a Queue
     */
    public void levelTraversal(Node root){
        Deque<Node> q = new ArrayDeque<Node>();
        q.add(root);
        while(!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.data);
            if(cur.left!=null)
                q.add(cur.left);
            if(cur.right!=null)
                q.add(cur.right);
        }
    }
  

Output of binary tree in zig-zag manner

The problem can be asked in different ways:

1. Given a binary tree and each node has an extra next pointer apart from left and right. Connect all the nodes using next pointer in Zig-Zag Manner.

2. Given a binary tree and each node has an extra next pointer apart from left and right. Print out all node in Zig-Zag Manner.

They are all coming down to how to traverse the binary tree in zig-zag manner. The key is to use two stacks, main stack and temporary stack. The main stack is used to traverse each layer, while put the children under the layer into temporary stack, also be careful with if we need to go left to right or right to left. 

public static void zigZag(Node root){

Stack<Node> s = new Stack<Node>();

s.add(root);

int level = 0;

Node pre = null;

while(!s.isEmpty()){

Stack<Node> t = new Stack<Node>();

while(!s.isEmpty()){

Node curr = s.pop();

if(pre==null)

pre = curr;

else{

pre.next = curr;

pre = curr;

}

if(level%2==0){

if(curr.left!=null)

t.add(curr.left);

if(curr.right!=null)

t.add(curr.right);

}else{

if(curr.right!=null)

t.add(curr.right);

if(curr.left!=null)

t.add(curr.left);

}

}

s = t;

level++;

}

}