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