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.
