[HN Gopher] The Great Tree-List Recursion Problem (2000) ___________________________________________________________________ The Great Tree-List Recursion Problem (2000) Author : nickdrozd Score : 38 points Date : 2021-11-01 14:36 UTC (8 hours ago) (HTM) web link (cslibrary.stanford.edu) (TXT) w3m dump (cslibrary.stanford.edu) | jhallenworld wrote: | 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. | mbf1 wrote: | Recursion / 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 wrote: | Are you assuming the tree is not read-only? | thor24 wrote: | By same order you mean as per in-order traversal correct? | cousin_it wrote: | Rotate 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? | derriz wrote: | The 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/ | mbf1 wrote: | I added next and previous pointers to my red-black tree | implementation for a freshman-level CS class back in 1997. It | enabled me to claim O(1) rather than O(lg N) to "find next value" | at an expense of a constant order of memory usage. Converting the | whole tree to a doubly linked list in O(N) time is cute. It's | also possible to re-construct a new balanced binary search tree | in O(N) time using O(N) memory. | | You'd start by counting the number of nodes in your circular | array O(N), and making an array of pointers to each node O(N), | then finding the middle node, which is the root node at count / | 2. You'd then re-link the nodes for a sub-array and recurse on | both sides using your in-order array of pointers, and replacing | the smaller and larger node pointers with the pointers from the | array. The total recursive algorithm visits each node in the new | tree only once. | hvasilev wrote: | I thought that flattening an ordered binary tree to a double- | linked list is a very common question asked on job interviews. | Personally I've seen the question twice on interviews so far. | dang wrote: | Some past threads: | | _The Great Tree-List Recursion Problem_ - | https://news.ycombinator.com/item?id=19324604 - March 2019 (21 | comments) | | _The Great Tree-List Recursion Problem (2000)_ - | https://news.ycombinator.com/item?id=15347519 - Sept 2017 (38 | comments) ___________________________________________________________________ (page generated 2021-11-01 23:01 UTC)