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.
