> 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.
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.