CareerCup

My solution was... Using doubly linked list to save the vertical sum.

findSum(TreeNode *p)
   if(p==NULL) return;
   n = newListNode(p->data)
   findVerticalSum(p,n);

findVerticalSum(TreeNode *p, ListNode *n)
  if(p==NULL) return;
  if(p->left!=NULL)
    if(n->prev!=NULL)
      n->prev->data += p->data;
    else
      ListNode *t = new ListNode(p->data);
      t->next=n; 
      n->prev = t;
    findVerticalSum(p->left, n->prev)

  if(p->right!=NULL)
    if(n->next!=NULL)
      n->next->data += p->data;
    else
      ListNode *t = new ListNode(p->data);
      t->prev=n; 
      n->next = t;
    findVerticalSum(p->left, n->next)

Let h = height of tree ---> takes O(log n) time
w = width of tree = 2*h+1

#define MAX_WIDTH 100
int vertical_sum[MAX_WIDTH]= {0};

void compute_vertical_sum(tree *node, int index, int width)
{
	if( node == NULL ) return;
	vertical_sum[index] += node->data;
	compute_vertical_sum( node->left, index-1, width);
	compute_vertical_sum( node->right, index+1, width);
}

in main():
        compute_vertical_sum (root, height, width);

	for(int i=0; i < width; i++) 
		if ( vertical_sum[i] > 0 )
			cout << vertical_sum[i] << "  " ;

vertical(Node *node, int flag) //flag can be left , right or both
{
if flag left or both
vertical (node->left, left);

FindVerticalLinesumfornode(node);

if flag right or both
vertical (node->right, right)
}

FindVerticalLinesumfornode(Node *node)
{
int sum=node->value;
int move=0 i=0;
tmp=node;
whlie (node) // first move left as i=0, then right then left add to the sum every alternate turn
{
if (i==0){
node=node->left
move++;
if(node && !(move &0x1)) sum+=node->value;
i=1
}
if (i==1){
node=node->right;
move++;
if(node && !(move &0x1)) sum+=node->value;
i=0
}
}
move=0; i=1;
node=tmp
whlie (node) //first move right as i=1, then right then left add to the sum every alternate turn
{
if (i==0){
node=node->left
move++;
if(node && !(move &0x1)) sum+=node->value;
i=1
}
if (i==1){
node=node->right;
move++;
if(node && !(move &0x1)) sum+=node->value;
i=0
}
}

printf (sum %d \t, sum);
}

call vertical with vertical(root, both) to print vertical sums in entire tree

please tell whats a vetical ?

I am just wondering if this will work.

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 column)
{
if(T==NULL) return;
Traverse(T.left, column-1);
Hash(column) += T.data;
Traverse(T.right, column+1);
}

Traverse(root, 0);
Print Hash

Using DP:
#include<iostream>
using namespace std;


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

void doprint(bt* root,int pos,int* ptr)
{
if(root == NULL)
return;
ptr[pos] = ptr[pos] + root->data;
doprint(root->left,pos-1,ptr);
doprint(root->right,pos+1,ptr);
}

void print(bt* root)
{
bt* lm = root->left;
bt* rm = root->right;

int lh = 0, rh =0;

while(lm != 0)
{
lm = lm->left;
lh++;
}

while(rm != 0)
{
rm = rm->right;
rh++;
}

int m = lh+rh;

int* ptr = new int[m+1];
for(int i = 0; i < m+1; ++i)
ptr[i] = 0;

doprint(root,lh,ptr);


for(int i = 0; i < m+1; ++i)
cout<<" "<<ptr[i];
cout<<endl;
}
int main()
{
bt* root = new bt();

root->data = 5;
root->left = new bt();
root->left->data = 3;
root->left->left = new bt();

root->left->left->data = 1;

root->left->right = new bt();;
root->left->right->data = 2;

root->right = new bt();;
root->right->data = 4;

root->right->right = new bt();

root->right->right->data = 6;
root->right->right->left = new bt();;
root->right->right->left->left = new bt();

root->right->right->left->data = 0;
root->right->right->left->left->data = 9;

print(root);

}

#include<iostream>
#include<stdio.h>
using namespace std;
struct node {
int n;
struct node * l[2]; };
struct node *curr= NULL;
struct node * insert ();
struct node * makenode (int n);
void inorder(struct node* , int);
void insert_dll(struct node *root, int i);
int main(){ int i;
struct node* root = NULL;
root = insert();
inorder(root, 2);
root= NULL;
while(curr->l[0]!= NULL) {
curr =curr->l[0]; }
while(curr!= NULL) {
cout<<curr->n<<endl;
curr = curr->l[1]; }
return 0;}
void inorder(struct node *root , int i ){
if ( root==NULL ){
return; }
insert_dll(root,i);
inorder(root->l[0], 0);
inorder(root->l[1],1);}
void insert_dll(struct node *root, int i){
struct node* tmp = NULL;
if (curr == NULL){
curr = makenode(root->n);}
else{
if (i==0){
if(curr->l[0]== NULL){
tmp = makenode(root->n);
curr->l[0]=tmp;
tmp->l[1]= curr;
curr= tmp;}
else{
curr->l[0]->n = curr->l[0]->n + root->n;
curr= curr->l[0];} }
else if (i==1){
if(curr->l[1]== NULL){
tmp = makenode(root->n);
curr->l[1]=tmp;
tmp->l[0]= curr;
curr= tmp;}
else{
curr->l[1]->n = curr->l[1]->n + root->n;
curr= curr->l[1];}}
if(root->l[0]==NULL && root->l[1]==NULL){
curr = curr->l[i+1];}}}
struct node * insert ( ){
struct node* root = NULL;
root = makenode(8);
root->l[0] = makenode(5);
root->l[1] = makenode(7);
root->l[0]->l[0] = makenode(6);
root->l[0]->l[1] = makenode(4);
root->l[0]->l[1]->l[0] = makenode(20);
root->l[1]->l[0] = makenode(3);
root->l[1]->l[1] = makenode(10);
root->l[1]->l[1]->l[0] = makenode(100);
return root; }
struct node * makenode (int n){
struct node *tmp;
tmp = new struct node;
tmp->n = n;
tmp->l[0] = NULL;
tmp->l[1] = NULL;
return tmp;}