Re: [algogeeks] Re: print vertical sums of a binary tree
initialize array with 0 and provide appropriate value to c otherwise
it will be negative and
here c is using as index for array.
procedure visit(node root,int s[],int c) {
if (root= null)
return 0;
S[c] += n.value;
visit(root->left, c - 1)
visit(root->right, c + 1)
}
On Fri, Oct 21, 2011 at 8:27 PM, ashish shukla
wrote:
> procedure visit(node root,int c) {
> if (root= null)
> return 0;
> S[c] += n.value;
> visit(root->left, c - 1)
> visit(root->right, c + 1)
> }
>
>
>
> On Fri, Oct 21, 2011 at 1:22 PM, Mohak Naik wrote:
>
>> If we want to compute the sum of every column, we can use the following
>> algorithm
>>
>> and call once visit(A, 0), where A is the root node. Note that S{...} in
>> the algorithm is a map whose keys are the columns numbers (..., -2, -1, 0,
>> 1, 2, ...) and whose values (at the end of the algorithm) are the sums of
>> the values of nodes in that column (S{1} will be the sum of nodes in
>> column 1). We can also use an array, instead of a map, provided that we pay
>> attention to the indexes (arrays have no negative indexes). The algorithm is
>> still O(n), because we traverse the entire tree only once. However, in this
>> case we need additional space to store the sum for all columns (the map, or
>> the array).
>>
>> stackoverflow solution.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: print vertical sums of a binary tree
procedure visit(node root,int c) {
if (root= null)
return 0;
S[c] += n.value;
visit(root->left, c - 1)
visit(root->right, c + 1)
}
On Fri, Oct 21, 2011 at 1:22 PM, Mohak Naik wrote:
> If we want to compute the sum of every column, we can use the following
> algorithm
>
> and call once visit(A, 0), where A is the root node. Note that S{...} in
> the algorithm is a map whose keys are the columns numbers (..., -2, -1, 0,
> 1, 2, ...) and whose values (at the end of the algorithm) are the sums of
> the values of nodes in that column (S{1} will be the sum of nodes in
> column 1). We can also use an array, instead of a map, provided that we pay
> attention to the indexes (arrays have no negative indexes). The algorithm is
> still O(n), because we traverse the entire tree only once. However, in this
> case we need additional space to store the sum for all columns (the map, or
> the array).
>
> stackoverflow solution.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: print vertical sums of a binary tree
If we want to compute the sum of every column, we can use the following
algorithm
procedure visit(node n, int c) {
if (n.left != null)
S{c} += n.value;
visit(n.left, c - 1)
visit(n.right, c + 1)
}
and call once visit(A, 0), where A is the root node. Note that S{...} in the
algorithm is a map whose keys are the columns numbers (..., -2, -1, 0, 1, 2,
...) and whose values (at the end of the algorithm) are the sums of the
values of nodes in that column (S{1} will be the sum of nodes in column 1).
We can also use an array, instead of a map, provided that we pay attention
to the indexes (arrays have no negative indexes). The algorithm is still
O(n), because we traverse the entire tree only once. However, in this case
we need additional space to store the sum for all columns (the map, or the
array).
stackoverflow solution.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: print vertical sums of a binary tree
You should use a doubly linked list instead of any sort of array. All the operation on the data structure you need are goto next/prev and insert front/end. Yunqiao On Wed, Oct 19, 2011 at 6:40 AM, monish001 wrote: > I think it might done using function of following prototype: > void func(node* root, deque& d, const deque::iterator& it); > > I will add left child's value in it-1 if exists else create new... > similarly for right child. > and call the same function for each of the children to explore > further.. > > Monish > > On Oct 15, 11:57 pm, SUMANTH M wrote: > > Hi, > > > >A binary tree is given we need to print vertical sums of nodes. for > > example > > > > 12 34 5 > > > > | | 5| | > > | | / | \ | | > > | | / |8 | > > | | / | / |\| > > | 4 |/| 10 > > |/ | \9| | > > | / | \ | | > > 7 | 6 | > > | | | | | > > | | | | | > > --- > > 7 4 20 8 10 > > > > Here we need to print sum 7,4,20,8,10. > > > > -Thanks > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: print vertical sums of a binary tree
I think it might done using function of following prototype: void func(node* root, deque& d, const deque::iterator& it); I will add left child's value in it-1 if exists else create new... similarly for right child. and call the same function for each of the children to explore further.. Monish On Oct 15, 11:57 pm, SUMANTH M wrote: > Hi, > > A binary tree is given we need to print vertical sums of nodes. for > example > > 1 2 3 4 5 > > | | 5 | | > | | / | \ | | > | | / | 8 | > | | / | / | \| > | 4 | / | 10 > | / | \ 9 | | > | / | \ | | > 7 | 6 | > | | | | | > | | | | | > --- > 7 4 20 8 10 > > Here we need to print sum 7,4,20,8,10. > > -Thanks -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: print vertical sums of a binary tree
On Tue, Oct 18, 2011 at 6:31 PM, rahul patil
wrote:
> Use recursion with the code as follows
>
>
sum array of sums, with horizontal levels, level 0 is for leftmost element
>
> void add(node *root, int *sum, int level)
> {
> if(root->left)
>
{
if(level != -1)
> level = add(root->left,sum, level-1);
>
else /* go till left with level =- 1 i.e uninitialized*/
> level = add(root->left,sum, level);
>
/*level of root is level of left node plus 1*/
level += 1;
}
/*set level =0 for leftmost element*/
if(level == -1)
level = 0;
/*level of right node is level of parent +1 */
if(root->right)
level = add(root->right,sum, level+1);
return level;
}
call with add(root, sum, -1);
>
>
>
> On Tue, Oct 18, 2011 at 8:58 AM, sravanreddy001
> wrote:
>
>> I that is what is suggested in the above code. Even here you can avoid the
>> sorting and add all with same x coordinate.. O(n) space as suggested..
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/CZ2rgqRAlW0J.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> Regards,
> Rahul Patil
>
--
Regards,
Rahul Patil
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: print vertical sums of a binary tree
Use recursion with the code as follows
void add(node *root, int *sum)
{
}
On Tue, Oct 18, 2011 at 8:58 AM, sravanreddy001 wrote:
> I that is what is suggested in the above code. Even here you can avoid the
> sorting and add all with same x coordinate.. O(n) space as suggested..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/CZ2rgqRAlW0J.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Regards,
Rahul Patil
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: print vertical sums of a binary tree
I that is what is suggested in the above code. Even here you can avoid the sorting and add all with same x coordinate.. O(n) space as suggested.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/CZ2rgqRAlW0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: print vertical sums of a binary tree
I have an alternate method. At every level, maintain records with (x-axis value, nodeValue) and keep them in a queue. After traversal is done, you can sort the elements based on x-Axis value and sum up the nodeValue for records having same x-axis value. But complexity is becoming O(nlogn) because of sorting. On Oct 16, 6:38 pm, sravanreddy001 wrote: > Even I see this as the best solution... > O(n) time and space.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
