3 ms·
This reminds of a similar problem: visit all nodes of a tree without using recursion or an explicit stack (or any extra storage). It's useful for marking live
by jhallenworld 5y ago
This reminds of a similar problem: visit all nodes of a tree without using recursion or an explicit stack (or any extra storage). It's useful for marking live nodes during mark & sweep garbage collection with a guarantee that the mark process itself will complete and not cause you to run out of memory.
So this is my amended problem: convert the tree to a same-ordered doubly-linked list without using recursion or an explicit stack.
- thor24 5y agoBy same order you mean as per in-order traversal correct?
- cousin_it 5y agoRotate right until there's nothing on the left, then step to the right child, append the former root to a doubly linked list, and repeat?
- mbf1 5y agoRecursion / Stacks are good for DFS traversals of a graph / tree. So maybe you could do a BFS traversal using a while loop and queue of nodes to process. I think that approach still doesn't save you any memory.
- dataflow 5y agoAre you assuming the tree is not read-only?
- klyrs 5y agoThe linked article modifies the tree in-place.
- derriz 5y agoThe solution to the first problem is the Joe Morris algorithm. I first came across it about 20 years ago and really struggled to visualize what was going on. [1] https://yuyuan.org/MorrisAlgorithm/ https://yuyuan.org/MorrisAlgorithm/