How can I show h(n) = O( √ n)?
Hint: Suppose that $n = 2^{2^k}$. Hence:

$$h(n) = h(2^{2^k} - 2^{2^{k-1}}) + 1 = h((2^{2^k} - 2^{2^{k-1}}) - \sqrt{2^{2^k} - 2^{2^{k-1}}}) + 1 + 1 = h(2^{2^k} - 2^{2^{k-1}} - 2^{2^{k-2}}\times \sqrt{2^{2^{k-1}}-1}) + 1 + 1$$

From the expansion, the order of $2^{2^{k-1}} = \sqrt{n}$ times is the length of the tree.