Vertical Sum of a Binary Tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-vertical-sum-in-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

1. Start with the root node and empty double list listNode
2. Add the value of the rootNode to the current listNode
3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively.
4. 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