Vertical Sum of a Binary Tree

Question : Find vertical sum of given binary tree.

Example:

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

The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7

To see more clearer picture :

Verticals of a Binary Tree

To understand what’s same vertical line, we need to define horizontal distances first. If two nodes have the same Horizontal Distance (HD) , then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.

Also, HD can be thought of as difference between right moves (r) - left moves (l) . So, for
node 1, r=0,l=0, HD=0
For node 2, l=1,r=0 , therefore HD=-1
For node 3, l=0,r=1, therefore HD =1
For node 4, r=0, l=2 therefore HD = -2
Fore node 5, r=1, l=1, therefore HD = 0

Solution 1: Using the hashmap

Define a dictionary (hash map) from HD to sum. And for each node you visit add its value to the dictionary key - this is a O(n) solution.
We can do an inorder traversal and hash the column. We call Traverse(root, 0) which means the root is at column 0. As we are doing our traversal, we can hash the column and increase its value by T.data. A rough sketch of my function looks like this -

Traverse(Tree T, int hd)  
{  
  if(T==NULL) return;  
  Traverse(T.left, column-1);  
  Hash(hd) += T.data;  
  Traverse(T.right, column+1);  
}

To begin with, Traverse will be called like

Traverse(root,0)

hd = 0 for root, so we passed 0.So, while calling left node, we decrease hd and opp for right node.

Here is the code in Java:

private void printVerticalSum(TreeNode root) {  
  
    // 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  
    printVerticalSumUtil(root, 0, hM);  
  
    // Prints the values stored by VerticalSumUtil()  
    if (hM != null) {  
        System.out.println(hM.entrySet());  
    }  
}  
  
// Traverses the tree in Inoorder form and builds a hashMap hM that  
// contains the vertical sum  
private void printVerticalSumUtil(TreeNode root, int hD,  
                                      HashMap<Integer, Integer> hM) {  
  
    // base case  
    if (root == null) {  return; }  
  
    // Store the values in hM for left subtree  
    VerticalSumUtil(root.left(), hD - 1, hM);  
  
    // Update vertical sum for hD of this node  
    int prevSum = (hM.get(hD) == null) ? 0 : hM.get(hD);  
    hM.put(hD, prevSum + root.key());  
  
    // Store the values in hM for right subtree  
    VerticalSumUtil(root.right(), hD + 1, hM);  
}

Solution2 : Using doubly link list

Here is the solution for doubly link list
Basic algo

Start with the root node and empty double list listNode
Add the value of the rootNode to the current listNode
Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively.
Similarly for right node, pass listNode.right and root.right

Pseudocode

node { sum = 0; node \*next=NULL; node \*prev=NULL; }   
  
printVerticalSum(TreeNode root)  
{  
   if(root==null)  
       return -1;  
    allocate node doubleLinkList //initialize,  
    printVerticalSumUtil(root, doubleLinkList);   
    //write the function to print double linked list  
    System.out.println(doubleLinkList.toString())  
}  
  
printVerticalSumUtil(TreeNode root, ListNode listNode)  
{  
  if(root==NULL) return;  
   
  if(root.left!=NULL)  
    if(listNode.prev!=NULL)  
      listNode.prev.data += root.data;  
    else  
      ListNode t = new ListNode(root.data);  
      t.next=listNode;   
      listNode.prev = t;  
    findVerticalSum(root.left, listNode.prev)  
   
  if(root.right!=NULL)  
    if(listNode.next!=NULL)  
      listNode.next.data += root.data;  
    else  
      ListNode t = new ListNode(root.data);  
      t.prev=listNode;   
      listNode.next = t;  
    findVerticalSum(root.right, listNode.next)  
}

Time complexity is O(n) in both the methods.

Thanks

Reference

http://stackoverflow.com/questions/14485255/vertical-sum-in-a-given-binary-tree

Solution 1: Using the hashmap

Solution2 : Using doubly link list

See also