Facebook: Print a Binary Tree Sum 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 PrintVerticalLevelNodesSum {
    
    /*
Output 
    
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,  

Output for sum
4,
2,
12,
11,
7
    */
     public static void main(String[] arg)
    {
        PrintVerticalLevelNodesSum tree = new PrintVerticalLevelNodesSum();
 
        /*
                    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);
        
        TreeMap mapSum = new TreeMap();
        printVerticalOrderSumUtilRecursive(root, 0, mapSum);
        
        // Print 
        System.out.println("vertical nodes :" );       
        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();
        System.out.println("vertical sum :" );
        for(Integer level: mapSum.keySet()){
            int tmp = mapSum.get(level);
            System.out.print(tmp + ",");
            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));
            }
        }        
    }   
    
    
    
    private static void printVerticalOrderSumUtilRecursive(TreeNode root, int level, TreeMap map) {
        // Base Case, root == null
        if(root == null) return;
        // Base Case, root != null
        int sum  = (map.get(level) != null)? map.get(level)+root.val: root.val;
        map.put(level, sum);
        // Recursive
        printVerticalOrderSumUtilRecursive(root.left, level-1, map);
        printVerticalOrderSumUtilRecursive(root.right, level+1, map);
    }
    
    private static void printVerticalOrderSumUtilInterative(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
            int sum = (map.get(entry.horizontalDistance) != null)? map.get(entry.horizontalDistance)+ root.val: root.val;
            map.put(entry.horizontalDistance, sum);          
            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));
            }
        }        
    }     
    
}

//list can not set -1, sum

//sh-4.3$ java -Xmx128M -Xms16M PrintVerticalLevelNodesSum                                                                                              
//Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0                                                                     
//        at java.util.ArrayList.rangeCheck(ArrayList.java:635)                                                                                         
//        at java.util.ArrayList.get(ArrayList.java:411)                                                                                                
//        at PrintVerticalLevelNodesSum.printVerticalOrderSumUtilRecursive(PrintVerticalLevelNodesSum.java:185)                                         
//        at PrintVerticalLevelNodesSum.printVerticalOrder(PrintVerticalLevelNodesSum.java:120)                                                         
//        at PrintVerticalLevelNodesSum.main(PrintVerticalLevelNodesSum.java:84)