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.