title: calculating the sum of nodes in a single verticle line of a binary tree
body: <p>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</p>
  
  <pre><code>             A
             /    \
            B      C
           /  \   /  \
           D   E  F   G
          / \ 
          H  I
  </code></pre>
  
  <p>IF you look at above tee </p>
  
  <pre><code>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
  </code></pre>
  
  <p>I implemented following algorithm</p>
  
  <pre><code>Map&lt;Integer,Integere&gt; mp = new HashMap&lt;Integer,Integer&gt;()
  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);
  
  }
  </code></pre>
  
  <ol>
  <li>I think the above algo is fine.Can
  any one confirm?</li>
  <li>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.</li>
  <li>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?</li>
  <li>Is the complexity of the above code
  i imolmeted is O(n)? (am not good at
  analysing time complexity , so
  asking )</li>
  </ol>