Facebook: Print a Binary Tree in Vertical Order

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map.Entry;
import java.util.Collections;


class QueueEntry
    {
        TreeNode node;
        int horizontalDistance;
        QueueEntry(TreeNode node, int horizontalDistance)
        {
            this.node = node;
            this.horizontalDistance = horizontalDistance;
        }
    }
class TreeNode
    {
        TreeNode left;
        TreeNode right;
        int val;
     
        public TreeNode(int x)
        {
            this.val = x;
        }
    }
    
public class PrintVerticalLevelNodes {
    
    /*
1. Expected Output -    
4
  2
  1  5  6
  3  8
  7    
2.  HashMap Output - 
 1,5,6,                                                                                                                                                 
8,3,                                                                                                                                                   
7,                                                                                                                                                     
4,                                                                                                                                                     
2,

3. TreeMap (key:level=>in order) Output
4,                                                                                                                                                     
2,                                                                                                                                                     
1,5,6,                                                                                                                                                 
8,3,                                                                                                                                                   
7,                                                                                                                                                     
   
4. Collections.sort() Output
4,                                                                                                                                                     
2,                                                                                                                                                     
1,5,6,                                                                                                                                                 
3,8,                                                                                                                                                   
7,  
    */
     public static void main(String[] arg)
    {
        PrintVerticalLevelNodes tree = new PrintVerticalLevelNodes();
 
        /*
                    1
              2           3
            4   5       6   7
                  8
         */
 
        TreeNode root = tree.createTree();
        tree.printVerticalOrder(root);
    }  
    public TreeNode createTree()
    {
        TreeNode root = new TreeNode(1);
        TreeNode n1   = new TreeNode(2);
        TreeNode n2   = new TreeNode(3);
        TreeNode n3   = new TreeNode(4);
        TreeNode n4   = new TreeNode(5);
        TreeNode n5   = new TreeNode(6);
        TreeNode n6   = new TreeNode(7);
        TreeNode n7   = new TreeNode(8);
 
        root.left  = n1;
        root.right = n2;
         
        n1.left  = n3;
        n1.right = n4;
             
        n2.left  = n5;
        n2.right = n6;
         
        n4.right = n7;
 
        return root;
    }
    // Main Function
    public static void printVerticalOrder(TreeNode root){
        if(root == null) return;
        //HashMap> map = new HashMap>();
        TreeMap> map = new TreeMap>();
        printVerticalOrderUtilRecursive(root, 0, map);
        //printVerticalOrderUtilInterative(root,0,map);
        // Print 
        for(Integer level: map.keySet()){
            ArrayList tmp = map.get(level);
            Collections.sort(tmp);
            for(Integer value: tmp)
                System.out.print(value + ",");
                System.out.println();
        }
        System.out.println();
    }
 
    //private static void printVerticalOrderUtil(TreeNode root, int level,
    // HashMap> map) {
    private static void printVerticalOrderUtilRecursive(TreeNode root, int level, TreeMap> map) {
        // Base Case, root == null
        if(root == null) return;
        // Base Case, root != null
        ArrayList list = (map.get(level) != null)? map.get(level): new ArrayList();
        list.add(root.val);
        map.put(level, list);
        // Recursive
        printVerticalOrderUtilRecursive(root.left, level-1, map);
        printVerticalOrderUtilRecursive(root.right, level+1, map);
    }
    
    private static void printVerticalOrderUtilInterative(TreeNode root, int level, TreeMap> map)
    {
        
        if (root == null) return;
         
        ArrayList mapEntry;
        LinkedList queue = new LinkedList();
        queue.add(new QueueEntry(root, level));
         
        while (!queue.isEmpty())
        {
            QueueEntry entry = queue.remove();
            // Base Case, root != null
            mapEntry = (map.get(entry.horizontalDistance) != null)? map.get(entry.horizontalDistance): new ArrayList();
            mapEntry.add(entry.node.val);
            map.put(entry.horizontalDistance, mapEntry);
            if (entry.node.left != null)
            {
                queue.add(new QueueEntry(entry.node.left, entry.horizontalDistance - 1));
            }
            if (entry.node.right != null)
            {
                queue.add(new QueueEntry(entry.node.right, entry.horizontalDistance + 1));
            }
        }        
    }    
    
}

if sum, no need for HashMap> ====> need int[] OR ArrayList => index is level and value is sum
list.set(level, list.get(level)+root.val);