Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

If the problem statement is still not clear to you, below is a pictorial representation of what you need to do:

i) an ordered binary tree (BST) storing numbers from 1 - 5.

ii) original tree converted to a sorted circular doubly-linked list. Its left and right pointers were modified to point to its previous and next node.

I originally read this interesting problem here: The Great Tree-List Recursion Problem.

Hint:
Think of in-order traversal. How do you ensure that the last element's right pointer points back to the first element?

A circular doubly-linked list. Think of the left and right pointers in a tree as synonymous to the previous and next pointers in a list.

Solution:
When I first see this problem, my first thought was in-order traversal. Couldn't we modify the nodes' left and right pointers as we do an in-order traversal of the tree? However, we have to beware not to modify the pointers and accessing it at a later time.

As we traverse the tree in-order, we could safely modify a node's left pointer to point to the previously traversed node as we never use it once we reach a node. We would also need to modify the previously traversed node's right pointer to point to the current node. Note: The previously traversed node meant here is not its parent node. It is the node's previous smaller element.

Easy approach, right? But wait, we are still missing two more steps. First, we did not assign the list's head pointer. Second, the last element's right pointer does not point to the first element (similar to the first element's left pointer).

How do we solve this? My approach is pretty easy: Just update the current node's right pointer to point back to the head and the head's left pointer to point to current node in each recursive call. As the recursion ends, the list's head and tail would be automagically updated with the correct pointers. Don't forget to check for this special case: A list with only one element should have its left and right pointers both pointing back to itself.

A double-linked list with a length of one.

Do you think this approach works? I bet it did! The run time complexity for this solution is O(N) since we are essentially doing a modified in-order traversal. It does have some extra assignments in each recursive call though. But overall I am quite satisfied with this approach because it is intuitive and easy to follow. Besides, we are adapting an existing algorithm (in-order traversal) to solve this problem, isn't this just neat?

// This is a modified in-order traversal adapted to this problem.
// prev (init to NULL) is used to keep track of previously traversed node.
// head pointer is updated with the list's head as recursion ends.
void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
    if (!p) return;
    treeToDoublyList(p->left, prev, head);
    // current node's left points to previous node
    p->left = prev;
    if (prev)
        prev->right = p;  // previous node's right points to current node
    else
        head = p; // current node (smallest element) is head of
    // the list if previous node is not available
    // as soon as the recursion ends, the head's left pointer
    // points to the last node, and the last node's right pointer
    // points to the head pointer.
    Node *right = p->right;
    head->left = p;
    p->right = head;
    // updates previous node
    prev = p;
    treeToDoublyList(right, prev, head);
}

// Given an ordered binary tree, returns a sorted circular
// doubly-linked list. The conversion is done in-place.
Node* treeToDoublyList(Node *root) {
    Node *prev = NULL;
    Node *head = NULL;
    treeToDoublyList(root, prev, head);
    return head;
}

Alternative Solution:
There is an alternative solution which doesn't use in-order traversal. Instead, it uses a divide and conquer method which is quite neat. I highly recommend you to read the solution (code provided) here.