Vertical Sum of Binary Tree

Question. Given a binary tree, print vertical sum of it.

As you can see in the example above, 4  2   12  3  7 are the vertical sum of the given binary tree.

Algo:

• Do the inorder traversal.
• Take a vari­able called vertical level, when ever you for left, do vertical level++ and when ever you go right do vertical level–.
• With step above we have separated out the levels vertically.
• Now you need to add the elements of each vertical level, so create a TreeMap and the (key,value) pair will be (level,Sum of elements).
• At the end iterate through the TreeMap and print the results

Solution#1:

public void VerticalSum(TreeNode T) {  
        // base case
        if (root == null) { 
             return; 
        }
  
        // Creates an empty hashMap hM
        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
  
        // Calls the VerticalSumUtil() to store the vertical sum values in hM
        VerticalSumUtil(root, 0, hM);
  
        // Prints the values stored by VerticalSumUtil()
        if (hM != null) {
            System.out.println(hM.entrySet());
        }
    }
  
// Traverses the tree in Inorder and builds a hashMap hM that contains the vertical sum
    private void VerticalSumUtil(TreeNode T, int vLevel,                                                          HashMap<Integer, Integer> hM) {
  
        // base case
        if (T== null) {  
             return;
        }
  
        // Store the values in hM for left subtree
        VerticalSumUtil(root.left, vLevel-1, hM);
  
        // Update vertical sum for vLevel of this node
        int prevSum = (hM.get(vLevel) == null) ? 0 : hM.get(vLevel);
        hM.put(vLevel, prevSum + T.val);
  
        // Store the values in hM for right subtree
        VerticalSumUtil(root.right, vLevel+ 1, hM);
    }



Solution#2:

public static TreeMap<Integer, Integer>treeMap = new TreeMap<Integer, Integer>();

public TreeNode verticalSum(TreeNode T, Integer vLevel){

  

 if(T == null)

   return null;

  

 TreeNode temp = verticalSum(T.left, --vLevel);

 if(temp == null)

    vLevel++;

  

 if(treeMap.get(vLevel) != null) {

   // add current node value to existing value in the map

   treeMap.put(vLevel, T.element + treeMap.get(vLevel));

 }

 else {

   // put current node value in the map

   treeMap.put(vLevel, T.element);

 }

  

  return verticalSum(T.right, ++vLevel);

}

  

 public void printVerticalSum(TreeMap<Integer, Integer> map) {

  for(Integer key : map.keySet()) {

      System.out.print(map.get(key) + " ");

  }

 }