5 ms·
The Great Tree-List Recursion Problem (2000)
- hvasilev 5y agoI 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.
- recursive 5y agoIn place though? I've never heard of it.
- dang 5y agoSome past threads: The Great Tree-List Recursion Problem - https://news.ycombinator.com/item?id=19324604 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 https://news.ycombinator.com/item?id=15347519 - Sept 2017 (38 comments)
- jhallenworld 5y agoThis 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/
- mbf1 5y agoI 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.
- icambron 5y agoI took a quick crack at this [1] and I have a few comments: 1. The double-linking and circularity make the solution uglier and more fiddly without making it really conceptually any harder. In particular, it means you end up mixing recursion with mutation, which is a little gunky. I wish they'd just have you output a single-linked list: same bang, less buck. 2. The problem mentions that the double-linked list nodes look a lot like the tree nodes, in the sense that they're a value with two pointers, but in practice that didn't have any effect on the solution, and I'm not really sure it's very interesting. 3. A thing that always comes up in these kinds of recursion problems is where to put the null checks, which in this case are a little complicated. I think neither my solution and the Java one in the link do a great job on that front [1] https://gist.github.com/icambron/4c03e1b19c3ca795d3930ed1720684af https://gist.github.com/icambron/4c03e1b19c3ca795d3930ed1720...
- cabalamat 5y agoIf I had to do this in production code I wouldn't do it that way (for a start I prefer static data structures where possible). I'd have 2 classes: BinaryTree and DoubleLinkedList, each of which would have a constructor that takes a list as input, and a function that returns the data as a list: class BinaryTree: def __init__(self, data: List): """ create from a list """ def asList(self)->List: """ return my data as a list """ class DoubleLinkedList: def __init__(self, data: List): """ create from a list """ def asList(self)->List: """ return my data as a list """ Then making a binary tree from a double-linked list is simply: BinaryTree(dll.asList())
- Kranar 5y agoThat's fair but it's trivial to convert a BinaryTree to a LinkedList (doubly or singly). If you eliminate the requirement that this must be done in-place (which implies O(1) auxilliary space), then the solution is not particularly interesting. The practical use case for in-place algorithms is operating on large data sets that are directly on a disk. Think some kind of database organizing data directly on a hard drive. You want to avoid having to double the number of hard drives you need in order to do some kind of data transformation, and perform any linking/relinking directly on the disk.
- cabalamat 5y ago> That's fair but it's trivial to convert a BinaryTree to a LinkedList (doubly or singly) If there's a way of doing it that's trivial, and another way that's complex, I will do it the trivial way unless there's a very good reason to do it the complex way. > The practical use case for in-place algorithms is operating on large data sets that are directly on a disk. Think some kind of database organizing data directly on a hard drive. I just hope the system doesn't crash while it's in the middle of doing it!
- anonygler 5y agoThis is just a LeetCode Medium. Amazed how twisted that site has made my brain. 2000 was so innocent.
- chakkepolja 5y agoHow much should I practice to get a twisted brain i.e solve Leetcode hard?