Binary Search Tree to Doubly linked list conversion

Introduction

In binary search tree, every node contains two pointers, one for left child and other for right child. Similarly, in doubly linked, every node contains two pointers, one for the next node and other for the previous node.

So can we convert a  binary search tree to a doubly linked list?

Problem statement

Given a binary search tree, convert this tree to a doubly linked list. Doubly linked list should be in sorted order.

For example, for below tree

Output should be

Analysis

Since doubly linked list is to be in sorted list, we need to traverse the tree in in-order traversal, which traverses nodes in sorted order. While doing in-order traversal we need to simultaneously modify pointers so that nodes points each other as per the definition of doubly linked list.

Let's say right pointer points to next node and left pointer points to previous node.

We need handle the left most node with care, as that node will be head of the resultant doubly linked list.

Algorithm

1. Start from the root
2. Traverse to left most node.
3. If this is the first node to be added in list, then mark this node as head and left pointer pointer to NULL.
4. Store node in step 3  as  last node visited.
5. Now traverse up and change left pointer of the last node (from the step 3) to the current node, change right pointer of current node to last node.
6. Change last as current.
7. If there is right child of current node, go to step 1 with right child as root node. 

Code

void treetoListRec(Node * node, Node ** last, Node **ptrToHead){

        if(node == NULL)
                return;
        /* Go to left most child */
        if(node->left)
                treetoListRec(node->left, last, ptrToHead);

        /* If this wasn't the first node being added to list*/  
        if(*last != NULL){
                (*last)->right = node;
        }
         else{
                 *ptrToHead = node; 
         }
        /*make left pointer point to last node, and update the 
          last node to current*/

        node->left = *last;
        *last = node;

        /* If there is right child, process right child */
        if(node->right)
                treetoListRec(node->right, last, ptrToHead);

}

Complexity analysis

This requires traversal of each node at least once, hence complexity analysis is O(N).

Note

There is one method, which takes into consideration that the whole problem can be divided into sub-problems involving left sub tree and right sub tree, once these sub problems are solved, we can combine solutions of these to come up with the solution of the bigger problem.

Basic idea is to convert left sub tree to doubly linked list, then convert right sub tree to doubly linked list and join both the lists with root in between. Idea is very well explained here

There is another way of converting tree to DDL, with zig-zag order. Code below does that

void treeToList(Node *node){

        Queue *queue = NULL;
        Node * last = NULL;
        if(node == NULL)
                return ;

        enqueue(&queue, node);
        while(!isEmpty(queue)){
        /* Take the first element and put both left and right              child on queue */
                node = front(queue);
                if(node->left)
                        enqueue(&queue, node->left);
                if(node->right)
                        enqueue(&queue, node->right);
                if(last != NULL)
                        last->right = node;
                node->left = last;
                last = node;
                dequeue(&queue);

        }

}