Vertical Sum of Binary Search Tree

Vertical Sum in Binary Tree

Given a binary search tree, find vertical sum of nodes which are at on the same vertical line. For example, in binary tree given below, nodes 6 and 5 are on same vertical line, where as node 7 and 9 are on different vertical lines. So sum of vertical line 3 in figure below will be 11 where as sum of vertical line 4 and 5 will be 7 and 9 respectively.

vertical sum of binary tree
If below tree is given as input, output should be like :

 
 Vertical Sum of line 1 = 2
 Vertical Sum of line 2 = 3
 Vertical Sum of line 3 = 11
 Vertical Sum of line 4 = 7
 Vertical Sum of line 5 = 9

Let’s consider root at vertical line 0, all vertical lines on left side of root will negative index and all on right side will be with positive index. To calculate sum on vertical lines, we have to traverse nodes on those line and store that. How do we know which vertical line we are at given point of time. There is an idea : when you  move towards left child of node, decrease index of vertical line and when  you move towards right child of node, increase index of vertical line. In this way, we always know at which vertical line we are at.

Mechanism will be same as level order printing of tree, for each movement towards left or right, we will either pass decreased or increased index of vertical line to recursive call. Whenever a node is a same vertical line, it will be added to the sum already calculated till now on that vertical line.

Only hurdle in this implementation is how to implement negative indices in an array. There are data structures like Hashmap available in high level languages which can solve this problem. However, in C we need to come up with some other way to store sum corresponding to each vertical line.
To make life simpler, we can have limit on number of vertical lines we can have in tree, lets call it HD_OFFSET. When we pass root to function call, we will map 0 index to HD_OFFSE/2. Sum of all vertical lines left of root will be stored between 0 to HD_OFFSET/2 and sum of all vertical lines on right side of root will be stored between index HD_OFFSET/2 to HD_OFFSET.

Implementation is very simple if you have understood recursive level order printing of binary search tree. Go through this post if you have doubt: Binary Search Tree : Level order printing

#include <stdio.h>
#include <stdlib.h>
 
#define HD_OFFSET 16
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
 
void verticalSum(Node *node, int hd, int sum[], int *min, int *max){
 
    /* We are offseting the index to access array correctly.
    Root will be at HD_OFFSET/2 index and all vertical lines on left will
    be at 0 to HD_OFFSET/2 and right side will be on HD_OFFSET/2 to HD_OFFSET */
 
    int index = hd + HD_OFFSET/2;
 
    if(!node) return;
 
    /* to keep track of min and max index filled in sum array */
    if(index > (*max)) (*max) = index;
    if(index < (*min)) (*min) = index;
 
    sum[index]+= node->value;
    /*If we are moving on the left side, 
    we will pass index as one less the current */
    verticalSum(node->left, hd-1, sum, min, max);
 
    /*If we are moving on the right side, 
    we will pass index as one more the current */
    verticalSum(node->right, hd+1, sum, min, max);
}
 
Node * createNode(int value){
    Node * newNode =  (Node *)malloc(sizeof(Node));
    newNode->value = value;
    newNode->right= NULL;
    newNode->left = NULL;
    return newNode;
}
 
Node * addNode(Node *node, int value){
    if(node == NULL){
        return createNode(value);
    }
    else{
        if (node->value > value){
            node->left = addNode(node->left, value);
        }
        else{
            node->right = addNode(node->right, value);
        }
    }
    return node;
}
 
//Driver program
int main(){
    int i;
    int sum[100] ={0, };
    int min = HD_OFFSET;
    int max = 0;
 
    Node *root = NULL;
    //Creating a binary tree
    root = addNode(root,6);
    root = addNode(root,3);
    root = addNode(root,2);
    root = addNode(root,1);
    root = addNode(root,7);
    root = addNode(root,5);
    root = addNode(root,9);
 
    verticalSum(root, 0, sum, &min, &max);
    for(i=min;i<=max; i++){
    	printf("Sum at vertical line %d : %d\n", i-min, sum[i]);
    }
 
    return 0;
}

Complexity of algorithm to fin vertical sum in binary search tree is O(N) as we traverse each node of tree at least once.

Please share your thoughts, if you like something or if you don’t like something. Sharing is caring. Spread the word and knowledge.

  • yuren1978

    why do need pass in min/max in the recursive function?

    • http://algorithmsandme.in/ Jitendra Sangar

      As we are filling our array of sums with middle index and move left of it in case of left tree w.r.t root and right of it in case of right sub tree w.r.t. root. So we don’t know how many indices we have moved left and right, to keep track of those,we use min and max index.
      If you look at the for loop where we do printing of sums, we are using i=min to i= max.

      • yuren1978

        Got it,thank you for explanation.

  • Kunal singh

    Sir,you have define HD_OFFSET as 16 in this case.can we have a more generic approach to this.if possible?where i dont have to predefine the horizontal distance.Also can we in the run time calculate the HD and then create a offset. Please correct me if i am on a wrong road :).
    Also please see this approach :

    void VerticalSum(Node *root,int col)//col=0 when first called
    {
    if(!root)
    return ;
    VerticalSum(root->left,col-1);
    Hash[col]++=root->data;
    VerticalSum(root->right,col+1);
    }

    i know there is a issue with indexing here but that is what i am looking to solve,in a generic way.Please Help.

    • http://algorithmsandme.in/ Jitendra Sangar

      HD_OFFSET can be calculated using diameter of the tree. As there will be no more vertical lines more than diameter of tree, hence instead of having HD_OFFSET as statically declare, you can have it dynamic and generic.
      Hope this help. Let me know if you need more clarifications.