A core point here is that the n/2 nodes and leaves are never touched.
   The subtree stays exactly the same until the max height increases by 1.
   This could be good to verify.
   Then, what data goes in updates after the first new leaf for a new
   root?