# 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.

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.