Print Vertical Sum of all the axis in the given binary Tree.
Most of times in written test , you will encounter this very good question.
given a binary tree.
(most of times a complete binary tree with all leaf node at same height will be given)
example :
Line 1: 4
Line 2: 2
Line 3: 1,5,6 =12
Line 4: 3
Line 5: 7
so Code should print 4,2,12,3,7
Adapt thinking pattern.
we need H alone, B,I and J should be together and so on...
so B,J,I should have same order/numbering or something...
First thought comes that we need height of tree, from there we can have some idea.
See when we print in order..it gives
4, 2, 5,1,6, 3, 7
Hence we can adapt In-Order traversal with some clustering/numbering so that we can print total with grouping
if you take height 3, see that if we multiply it by 2 ( as we have left and right subtrees)
we get 6.
In In-Order traversal when we start from root, we pass level 8.
At every left subtree call we can reduce it by one, and at right subtree call we can increase.
and hence what we get..
Inorder : 4, 2, 5,1,6, 3, 7
level : 4, 5 , 6,6,6 , 7 , 8
Hence we concluded that We can sum all node->data who has same level.
Code :
Thanks to Dhaval for suggesting this approach
example :
1 A
/ \
/ \
/ \
2 B 3 C
/ \ / \
/ \ / \
4 D 5 E 6 F 7 G
For the above tree, Vertical sum should be calculated as follows,Line 1: 4
Line 2: 2
Line 3: 1,5,6 =12
Line 4: 3
Line 5: 7
so Code should print 4,2,12,3,7
Adapt thinking pattern.
we need H alone, B,I and J should be together and so on...
so B,J,I should have same order/numbering or something...
First thought comes that we need height of tree, from there we can have some idea.
See when we print in order..it gives
4, 2, 5,1,6, 3, 7
Hence we can adapt In-Order traversal with some clustering/numbering so that we can print total with grouping
if you take height 3, see that if we multiply it by 2 ( as we have left and right subtrees)
we get 6.
In In-Order traversal when we start from root, we pass level 8.
At every left subtree call we can reduce it by one, and at right subtree call we can increase.
and hence what we get..
Inorder : 4, 2, 5,1,6, 3, 7
level : 4, 5 , 6,6,6 , 7 , 8
Hence we concluded that We can sum all node->data who has same level.
Code :
Thanks to Dhaval for suggesting this approach
void Vsum(struct node *temp, int level, int count[])
{
if(temp)
{
Vsum(temp->left, level-1, count);
count[level] += temp->data;
Vsum(temp->right, level+1, count);
}
return;
}
int height(struct node * root)
{
struct node *temproot = root;
int i=0,j=0;
while(temproot->left != NULL)
{
i++;
tmproot = tmproot->left;
}
while(temproot->right != NULL)
{
j++;
tmproot = tmproot->left;
}
if(i>j) return 2*i ;
else return 2*j ;
}