> Or for a possibly more useful comment, constant space tree traversal is genuinely quite difficult to implement. I don't know a general solution to it (other than walk from the start N times, quadratic style), would be interested to hear of one.
There's Morris tree traversal. It basically turns an ordinary binary tree into a threaded binary tree and fixes it up after it's done. But, this is mainly possible because of the space wasted by the null pointers at the leaves of the tree. You can hide a stack within the tree.
There's Morris tree traversal. It basically turns an ordinary binary tree into a threaded binary tree and fixes it up after it's done. But, this is mainly possible because of the space wasted by the null pointers at the leaves of the tree. You can hide a stack within the tree.