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 mohak...@gmail.com 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
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
ashishshukla0...@gmail.comwrote:
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 mohak...@gmail.com 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.
[algogeeks] Re: print vertical sums of a binary tree
I think it might done using function of following prototype: void func(node* root, dequeint d, const dequeint::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 sumanth.n...@gmail.com 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
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 monish.gup...@gmail.com wrote: I think it might done using function of following prototype: void func(node* root, dequeint d, const dequeint::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 sumanth.n...@gmail.com 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.
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 sravanreddy...@gmail.comwrote:
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.
Re: [algogeeks] Re: print vertical sums of a binary tree
On Tue, Oct 18, 2011 at 6:31 PM, rahul patil
rahul.deshmukhpa...@gmail.comwrote:
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
sravanreddy...@gmail.comwrote:
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.
[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 sravanreddy...@gmail.com 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.
[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.
