Great-Tree-List-Recursion Problem

It involves conversion of an ordered binary tree into a Doubly Linked List.

The problem will use two data structures -- an ordered binary tree and a circular doubly linked list. Both data structures store sorted elements, but they look very different.

1. Ordered Binary Tree

In the ordered binary tree, each node contains a single data element and "small" and "large" pointers to sub-trees (sometimes the two pointers are just called "left" and "right"). Here's an ordered binary tree of the numbers 1,2,3,4,5,7,8.

All the nodes in the "small" sub-tree are less than or equal to the data in the parent node. All the nodes in the "large" sub-tree are greater than the parent node. So in the example above, all the nodes in the "small" sub-tree off the 4 node are less than or equal to 4, and all the nodes in "large" sub-tree are greater than 4. That pattern applies for each node in the tree. A null pointer effectively marks the end of a branch in the tree. Formally, a null pointer represents a tree with zero elements. The pointer to the topmost node in a tree is called the "root".

2. Circular Doubly Linked List

Here's a circular doubly linked list of the numbers 1,2,3,4,5,7,8.

The circular doubly linked list is a standard linked list with two additional features...

• "Doubly linked" means that each node has two pointers -- the usual "next" pointer that points to the next node in the list and a "previous" pointer to the previous node.
• "Circular" means that the list does not terminate at the first and last nodes. Instead, the "next" from the last node wraps around to the first node. Likewise, the "previous" from the first node wraps around to the last node.

We'll use the convention that a null pointer represents a list with zero elements. It turns out that a length-1 list looks a little silly...

The single node in a length-1 list is both the first and last node, so its pointers point to itself. Fortunately, the length-1 case obeys the rules above so no special case is required.

The Trick -- Separated at Birth?

Here's the trick that underlies the Great Tree-List Problem: look at the nodes that make up the ordered binary tree. Now look at the nodes that make up the linked list. The nodes have the same type structure -- they each contain an element and two pointers. The only difference is that in the tree, the two pointers are labeled "small" and "large" while in the list they are labeled "previous" and "next". Ignoring the labeling, the two node types are the same.

---

3. The Challenge

The challenge is to take an ordered binary tree and rearrange the internal pointers to make a circular doubly linked list out of it. The "small" pointer should play the role of "previous" and the "large" pointer should play the role of "next". The list should be arranged so that the nodes are in increasing order...

This drawing shows the original tree drawn with plain black lines with the "next" pointers for the desired list structure drawn as arrows. The "previous" pointers are not shown. 

4. Problem Statement

Here's the formal problem statement: Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The "previous" pointers should be stored in the "small" field and the "next" pointers should be stored in the "large" field. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list. The operation can be done in O(n) time -- essentially operating on each node once. Basically take figure-1 as input and rearrange the pointers to make figure-2.

Try the problem directly, or see the hints below.

---

Hints

Hint #1

The recursion is key. Trust that the recursive call on each sub-tree works and concentrate on assembling the outputs of the recursive calls to build the result. It's too complex to delve into how each recursive call is going to work -- trust that it did work and assemble the answer from there.

Hint #2

The recursion will go down the tree, recursively changing the small and large sub-trees into lists, and then append those lists together with the parent node to make larger lists. Separate out a utility functionappend(Node a, Node b) that takes two circular doubly linked lists and appends them together to make one list which is returned. Writing a separate utility function helps move some of the complexity out of the recursive function.