array algorithms - calcuating the sum of nodes in a single verticle line of a binary tree -

for binary tree want sum of nodes fall in single verticle line.i want sum of nodes in each verticle node

                        /    \           b      c          /  \   /  \          d   e  f   g         / \          h  

if @ above tee

line 0    e f   sum  = a+e+f line -1  b      sum = b +i line 1   c        sum = c line 2   g        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 above algo fine.can 1 confirm?
2. also how can without using hashmap,arraylist or such collection datatype of java.one method 2 two arrays 1 storing negative indexes(mapped positive) , 1 positive indexs(right side of root).but dont know size of array be.
3. one approach use doubly link list , add node on right/left movement if necessary. not getting how can implement approach? other simple/more time efficient approach?
4. is complexity of above code imolmeted o(n)? (am not @ analysing time complexity , asking )

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 requirements, here suggested code. note c++'ish , not using java's or c++'s standard api lists, should idea. assume addnodebefore , 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; }