title: Algorithm- Sum of distances between every two nodes of a Binary Search Tree in O(n)?
body: <p>The question is to find out sum of distances between every two nodes of BinarySearchTree given that every parent-child pair is separated by unit distance. It is to be calculated after every insertion.</p>
  
  <p>ex:</p>
  
  <pre><code> -&gt;first node is inserted..
  
        (root)
  
     total sum=0;
  
  -&gt;left and right node are inserted
  
        (root)
        /    \
    (left)   (right)
  
     total sum = distance(root,left)+distance(root,right)+distance(left,right);
               =        1           +         1          +         2
               =     4
  
  and so on.....
  </code></pre>
  
  <p>Solutions I came up with:</p>
  
  <ol>
  <li><p>Brute-force. Steps:</p>
  
  <ol>
  <li>perform a DFS and track all the nodes : <code>O(n)</code>.</li>
  <li>Select every two nodes and calculate  : <code>O(nC2)_times_O(log(n))=O(n2log(n))</code> distance between them using <a href="http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/">Lowest Common Ancestor</a> Method and add them up.</li>
  </ol>
  
  <p>Overall Complexity: <code>-O(n2log(n))</code>.  </p></li>
  <li><p><code>O(nlog(n))</code>. Steps:-</p>
  
  <ol>
  <li>Before insertion perform DFS and track all nodes : <code>O(n)</code>.</li>
  <li>Calculate distance between the inserted node and : <code>O(nlog(n))</code>. the remaining nodes.</li>
  <li>Add the existing sum with the sum calculated in step 2</li>
  </ol>
  
  <p>Overall Complexity: <code>-O(nlog(n))</code>.</p></li>
  </ol>
  
  <p>Now the question is "is there any solution exists of order of <code>O(n)</code>??</p>