Create a list of Vertical sum of a given binary tree.

A simple recursive solution would be sufficient enough to solve this.

The approach is to weight each node in the tree as below, starting with root node's weight as 0.

1. Weight of the left child of the node will be less than weight of the root by one.
2. Weight of the right child of the node will be more than weight of the root by one.

By this way the whole tree can be weighted,
and now Sum up all the nodes with same weight which gives the vertical sum of the column of nodes.

Below is implementation, and the results can be stored in either array or list or any DS.

/*
Q: Create a list of Vertical sum of a given binary tree.
*/

struct node{
 int data;
 struct node* left;
 struct node* right;
}

int getHeightOfTree(struct node* root){
 if(root==NULL){
  return -1;
 }
 int l= getHeightOfTree(root->left);
 int r= getHeightOfTree(root->right);
 return ((l>r)?(l+1):(r+1));
}


void buildVerticalSum(struct node* root, int A[], int h, int w){
 if(root!=NULL){
  buildVerticalSum(root->left,A,h,w-1);
  A[h+w]+=root->data;
  buildVerticalSum(root->right,A,h,w+1);
 }
}

/* Array A will have vertical sums of the tree. This can be modified to create a list. Or in Other DS*/
void verticalSum(struct node* root){
 int h=getHeightOfTree(root);
 
 int* A=NULL;
         A=(int*)malloc(sizeof(int)*(2*h+1));
 
 buildVerticalSum(root,A,h,0);
 
 for(int i=0;i<2*h+1;i++){
  printf(“%d ”,A[i]);
 }
 printf(“\n”); 
 
}