I really like that the hint is optional. You don't always want the hint because if you're jumping d steps ahead, you actually need to touch 2 log(d) nodes, onc

I really like that the hint is optional. You don't always want the hint because if you're jumping d steps ahead, you actually need to touch 2 log(d) nodes, once to walk up, and another to walk down. This means anytime you're moving more than d=sqrt(n) steps away you're better off just walking down from the root instead. For example if n=1000000, if the hot section is wider than d=1000, you're better off going from root all the time. Of course if you access stuff that are directly adjacent you should still use inorder iteration for those (but I see that as a ++ operator, not a separate lookup).