title: Vertical Sum in a given Binary Tree
body: <p>Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.</p>
  
  <p>To understand what's same vertical line, we need to define horizontal distances first. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.</p>
  
  <p>Examples:</p>
  
  <pre><code>    1
    /   \
   2     3
  / \   / \
  4  5  6  7
  </code></pre>
  
  <p>The tree has 5 vertical lines</p>
  
  <p>Vertical-Line-1 has only one node 4 => vertical sum is 4</p>
  
  <p>Vertical-Line-2: has only one node 2=> vertical sum is 2</p>
  
  <p>Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12</p>
  
  <p>Vertical-Line-4: has only one node 3 => vertical sum is 3</p>
  
  <p>Vertical-Line-5: has only one node 7 => vertical sum is 7</p>
  
  <p>So expected output is 4, 2, 12, 3 and 7</p>
  
  <p><em><strong>My solution:</em></strong>
  I think out a o(nlong(n)) solution for this problem. The idea is:</p>
  
  <p>(1) using preorder traversal to get the HD for every node, and store the HD and its associated node in an array.</p>
  
  <p>(2) sort the array by HD</p>
  
  <p>(3) traversal the sorted array to print result.</p>
  
  <p>I'm sure this is not the best one for this problem. Can anyone help me give a better solution?</p>