title: Finding the smallest number of nodes that must be added to make a binary tree balanced?
body: <p>Suppose that you are given an arbitrary binary tree.  We'll call the tree <em>balanced</em> if the following is true for all nodes:</p>
  
  <ol>
  <li>That node is a leaf, or</li>
  <li>The height of the left subtree and the height of the right subtree differ by at most ±1 and the left and right subtrees are themselves balanced.</li>
  </ol>
  
  <p>Is there an efficient algorithm for determining the minimum number of nodes that need to be added to the tree in order to make it balanced?  For simplicity, we'll assume that nodes can only be inserted as leaf nodes (like the way that a node is inserted into a binary search tree that does no rebalancing).</p>