[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)