title: Average distance of a node from root in weighted quick union algorithm?
body: <pre><code>Compute the average distance from a node to the root in a worst-case tree of 
  2^n nodes built by the weighted quick union algorithm?
  </code></pre>
  
  <p>This is an exercise in Algorithm in C++(Robert Sedgewick).</p>
  
  <p>I know the worst case distance but can someone suggest me correct way to compute average distance?</p>
  
  <p>Worst case scenario is the merging of 2 tree with same number of nodes. lets say merge 2 tree each having 2^n nodes, resulting tree [=size 2^(<b>n+1</b>) nodes] will have <b>n+1 max</b> distance of any node from the root ( more than 1 after merge).</p>
  
  <p><b>In worst case-  if tree size is 2^n, distance from root to any of the node is always less than n.</b></p>
  
  <p>How can we calculate the average distance if the max distance is n for 2^n node tree?</p>