[AMAZON] Vertical sum of nodes
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples:
1
/ \
2 3
/ \ / \
4 5 6 7The tree has 5 vertical lines
Vertical-Line-1 has only one node 4 => vertical sum is 4
Vertical-Line-2: has only one node 2=> vertical sum is 2
Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12
Vertical-Line-4: has only one node 3 => vertical sum is 3
Vertical-Line-5: has only one node 7 => vertical sum is 7
So expected output is 4, 2, 12, 3 and 7
A Binary tree can have all the elements aligned in a linear way.so if we assign root as vertical line 1 then its left child will be -1 and right will be +1.so either create a map stl and update the sum at each level corresponding to its own line number.
ReplyDeleteget_Vertical_Sum(Tree* t,int level)
{
if(t==NULL)
return;
else
{
verticalSum[level]+=T->data;
get_Vertical_Sum(T->left,level-1);
get_Vertical_Sum(T->right,level+1);
}
}
A better solution without using stl is create an array of 2*h+1 elements where h is height of tree, then rest logic will be same.
ReplyDeleteWhy we will create an array of size 2*h+1.it also invlolves finding the height of tree.
ReplyDeleteBetter approach may be->
Find the total no. of vertical lines this way ->
Use Inorder DFS to find the distance of leftmost node from root and distance of rightmost node from root
Total vertical lines= leftdistance + 1 + rightdistance
Now fill the array using same logic of +1,-1.
Time Complexity still remains - O(n)
1
ReplyDelete/ \
2 3
/ \ / \
4 5 6 7
/
8
in this case height of tree is 3..but number of vertical lines are same .so in this case 2*h+1 = 2*3+1 =7 which will give grabage value.
8 is left child of 5.
ReplyDelete@navin- left most +right most +1 ... will also not give exact number of vertical sum if 8 has left child 99 and 99 has left child 100 and 100 has left child 101.
ReplyDelete@Anonymous when you create an array of 2*h+1, initially fill all the index with value INT_MIN or NaN so that after traversing the elements you can know how many of them are filled with the values of nodes and how many of them are not visited...
ReplyDeletevoid get_Vertical_Sum(Tree* T,int i)
{
if(T==NULL)
return;
else
{
if (verticalSum[i] == INT_MIN)
verticalSum[i] = 0;
verticalSum[i]+=T->data;
get_Vertical_Sum(T->left,i-1);
get_Vertical_Sum(T->right,i+1);
}
}
sorry i am not getting it. my question was to related to size of verticalSum array. if we give its size 2*h+1 then in my above comment (in which 8 is left child of 5) it build total 2*3+1 =7 . and when we print value of verticalSum through loop.
Deletefor(i=0;i<2*h+1;i++)
print value of verticalSum[i];
it gives total 7 value but still we have only 5 value of verticalSum.please correct me if i am wrong.
@Anonymous yeah you are right even though there will be 7 entries in the array, but all the entries will be initialized to INT_MIN, which we expect will not occur as a sum in the tree.so when you print the array you will skip those entries whose value is still INT_MIN.
Deleteyeah..as i said we have to skip. actually i wanted to create a big enough memory to verticalSum, as use of space is always constraint.i just want to give array size equal to exact number of vertical lines.
Delete@Anonymous count the number of columns first then create an array of exactly max-min+1 size.This function basically counts the distance of left most node and right most node from root.Initially assign min = INT_MAX, max = INT_MIN and i = 0.Hope this clears ur doubt...please comment.
Deletevoid Count_Columns(Tree* pNode, int i, int& min, int& max)
{
if (!pNode)
return;
Count_Columns(pNode->left, i-1, min, max);
min = ::min(i, min);
max = ::max(i, max);
Count_Columns(pNode->right, i+1, min, max);
}
@Navin please comment how will you find leftmost node and rightmost node...
ReplyDeletefor leftmost and right most node.. we can use dfs .but it failed to count exact number of vertical sum .
ReplyDelete@All
ReplyDeletemy question is you need to store the vetical sum in a doubly Linked List ? your function should be returning the head of doubly Linked List
Thank you