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;
}