calculating the sum of nodes in a single verticle line of a binary tree

Question

For a binary tree i want to get the sum of all nodes that fall in a single verticle line. I want the sum of nodes in each verticle node

             A
           /    \
          B      C
         /  \   /  \
         D   E  F   G
        / \ 
        H  I

IF you look at above tee

line 0   A  E F   so sum  = A+E+F
line -1  B I      so sum = B +I
line 1   C        so sum = C
line 2   G        so sum = G

I implemented following algorithm

Map<Integer,Integere> mp = new HashMap<Integer,Integer>()
calculate(root,0); 

 void calculate(Node node, int pos){
   if(node==null)
        return ;
  if(mp.containsKey(pos) ){
    int val = mp.get(pos) + node.data;
     mp.put(pos,val);
    }
    else{ 
         mp.put(pos,node.data);
    }

    calculate(node.left,pos-1);
    calculate(node.right,pos+1);

}

1. I think the above algo is fine.Can any one confirm?
2. Also how can i do it without using HashMap,arraylist or any such collection datatype of java.One method is two is 2 arrays one for storing negative indexes(mapped to positive) and one for positive indexs(right side of root).But we dont know what the size of array will be.
3. One approach is to use doubly link list and add a node on right/left movement if necessary. Am not getting how can i implement this approach? Any other simple/more time efficient approach?
4. Is the complexity of the above code i imolmeted is O(n)? (am not good at analysing time complexity , so asking )

Answer 1

C++ code

int vertsum(Node* n, int cur_level, int target_level)
{
  if (!n)
    return 0;

  int sum = 0;
  if (cur_level == target_level)
    sum = n->value;
  return sum + 
         vertsum(n->left, cur_level-1, target_level) + 
         vertsum(n->right, cur_level+1, target_level);
}

invocation example:

vertsum(root, 0, 1);

EDIT:

After clarifying the requirements, here the suggested code. Note that this is C++'ish and not exactly using Java's or C++'s standard API for lists, but you should get the idea. I assume that addNodeBefore and addNodeAfter initialize node's data (i.e. ListNode::counter)

void vertsum(TreeNode* n, int level, ListNode& counter)
{
  if (!n)
    return;

  counter.value += n->value;
  counter.index = level;

  if (! counter.prev)
    addNodeBefore(counter);
  vertsum(n->left, level-1, counter.prev);             

  if (! counter.next)
    addNodeAfter(counter);
  vertsum(n->right, level+1, counter.next);

  return;
}

Answer 2

You could visit the binary tree in depth-first postorder, and use an offset to keep track of how far you moved to the left/right with respect to your starting node. Every time you move to the left, you decrement the offset, and every time you move to the right you increment the offset. If your visit procedure is called with an offset of 0, then it means that the node being visited has the same offset of your starting node (i.e. it's in the same column), and so you must add its value.

Pseudocode:

procedure visit (node n, int offset) {
  sumleft = 0
  sumright = 0
  if (n.left != null)
    sumleft = visit(n.left, offset - 1)
  if (n.right != null)
    sumright = visit(n.right, offset + 1)
  if (offset == 0)
    return n.value + sumleft + sumright
  else
    return sumleft + sumright;
}

For example, if you call

visit(A, 0)

you will get the following calls:

visit(A, 0) -> E.value + F.value + A.value
  visit(B, -1) -> E.value
    visit(D, -2) -> 0
      visit(H, -3) -> 0
      visit(I, +2) -> 0
    visit(E, 0) -> E.value
  visit(C, +1) -> F.value
    visit(F, 0) -> F.value
    visit(G, +1) -> 0

Another example, starting from node B:

visit(B, 0)
  visit(D, -1) 
    visit(H, -2)
    visit(I, 0) -> here we return I.value
  visit(E, +1)

when recursion goes back to the initial call visit(B, 0) we have sumleft = I.value and sumright = 0, so we return the final result B.value + I.value, as expected.

Complexity of O(n), because you visit once all nodes of your tree rooted at the starting node.

---

After think about the above algorithm, I realize it has a limitation, which becomes evident when we consider a more complex tree like the following:

In this case visit(B, 0) would still return B.value + I.value, but this is not the expected result, because N is also on the same column. The following algorithm should cope with this problem:

procedure visit(node n, int c, int t) {
  sumleft = 0;
  sumright = 0;
  if (n.left != null)
    sumleft = visit(n.left, c - 1, t)
  if (n.right != null)
    sumright = visit(n.right, c + 1, t)
  if (c == t)
    return n.value + sumleft + sumright;
  else
    return sumleft + sumright;
}

The idea is essentially the same, but we have now a parameter c which gives the current column, and a parameter t which is the target column. If we want the sum of the elements in the B column, then we can call visit(A, 0, -1), that is we always start our visit from node A (the root's tree), which is at column 0, and our target is column -1. We get the following:

Therefore visit(A, 0, -1) = B + I + N as expected.

Complexity is always O(n), where n is the number of nodes in the tree, because we visit the entire tree with depth-first postorder, and we process each node only once.

---

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). If I'm not mistaken a binary tree of height h will have 2*h + 1 columns.