News for hackers. Stuff that matters.
Re:Tree traversal without recursion: the tree as a state mac... by derriz on Tuesday September 03, 2019 @06:43AM (#20865266)
> You can get rid of any stacks whatsoever by keeping a parent pointer in the tree node data structure.

You can actually in-order traverse a binary tree without any memory overhead at all (no parent pointer nor an implicit or explicit stack) using Joe Morris' traversal.

I found that this can be done to be surprising but effectively it uses the NULL slots as temporary storage.

Here's one explanation: https://yuyuan.org/MorrisAlgorithm/ - although there seem to be a few youtube videos on it also.

There are no comments on this comment yet.