The Great Tree-List Recursion Problem (2000)

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.

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)

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.

I 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/4c03e1b19c3ca795d3930ed1720...

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.

This is just a LeetCode Medium. Amazed how twisted that site has made my brain. 2000 was so innocent.

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