Convert Binary Tree to Doubly linked list

Convert Binary Tree to Doubly linked list (BST To DLL)

In binary search tree, each node contains two pointers, one for left child and other for right child. Similarly, in a doubly linked, each node contains two pointers, one for next node and other for previous node. It would be interesting to covert one type to another, wouldn’t it. Problem statement is convert binary tree to doubly linked list, or in short convert a bst to dll.  There can be different ways in which a tree can be converted into a doubly linked list and based on traversal order, order of nodes in resultant doubly linked would be different. For example, for below binary search tree, if we chose inorder traversal, resultant doubly linked list will be in sorted order

convert binary tree to doubly linked list

Output would be this doubly linked list.

bst to dll convert

First of all, decide what is correlation between given input and output generated. Let’s say, left pointer of node will point to previous node, and right pointer of node in BST will point to next node in DLL.

To convert binary tree to doubly linked list, traverse binary tree in inorder manner and at each node, link left pointer of current node to inorder predecessor. Since we decided that left pointer will point to previous node, previous node of current node will be the node which was visited just before current node in traversal. Hence, link left pointer of current node to inorder predecessor.

Inorder traversal gives opportunity to change current node’s left pointer to point to previous node as in inorder traversal we will never need to traversal left subtree of current node again.

There are two extra things need to be done apart from traversing tree are:
1. Keep track of the head pointer of the resultant DLL. Head pointer will be updated when left most node of tree is visited. At this time last pointer will be NULL as this is first node being inserted into doubly linked list.

In short, the left most leaf of BST will be head of DLL and it’s previous pointer will point to NULL as there is no inorder predecessor of that node.
2. Keep track last pointer, so that current pointer’s left can point to last pointer which will be previous node of current node in DLL. After processing each node, last pointer is updated to point current node.

Algorithm to covert binary tree to doubly linked list

1. Do inorder traversal of tree.
2. In process step, do following :
2.1 If this is the first node to be added in list, then mark this node as head and left pointer pointer to NULL.
2.2 Point current node's left pointer to last node. Also update right pointer of last node to point to current node.
2.3 Update last pointer to point to current node.

Convert a BST to DLL : C implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
        int value;
        struct node *left;
        struct node *right;
};
typedef struct node Node;
 
void treetoListRec(Node * node, Node ** last, Node **ptrToHead){
        if(!node)
           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);
 
}

Node * createNode(int value){
        Node * newNode =  (Node *)malloc(sizeof(Node));
        newNode->value = value;
        newNode->right= NULL;
        newNode->left = NULL;
        return newNode;
}

Node * addNode(Node *node, int value){
        if(!node) return createNode(value);
        if (node->value > value)
            node->left = addNode(node->left, value);
        else
            node->right = addNode(node->right, value);

        return node;
}
 
/* Driver program for the function written above */
int main(){
        Node *root = NULL;
        Node * last = NULL;
        Node *ptrToHead = NULL;

        //Creating a binary tree
        root = addNode(root,30);
        root = addNode(root,20);
        root = addNode(root,15);
        root = addNode(root,25);
        root = addNode(root,40);
        root = addNode(root,37);
        root = addNode(root,45);
 
        treetoListRec(root,&last, &ptrToHead);
 
        return 0;
}

Implementation is nothing but inorder traversal of binary search tree. Traversal order is : Left sub tree, root node and right sub tree. Traverse left sub tree till the time left most node of tree is encountered, call it current node. This node will be head of doubly linked list being generated. At this point of time, since no node has been added to dll, last pointer will be NULL.  Update head reference to point to current node and last pointer reference also to point to current node.

Before updating the last node, we need to make sure that current node’s left pointer points to last node and if last node is not null, then last node’s right point should point to current node. If there is right sub tree of node, current node becomes last node visited and then right sub tree is visited in same manner as we started from root, now root being the right child of current node. Hope this clarifies the code, if you have some doubt, please leave a comment.

Conversion of BST to DLL requires traversal of each node at least once, hence complexity is O(N). There is inherent space requirement for stack as O(N) in case the tree is completely skewed and O(log N) is tree is balanced.

Note

There is one more method to convert a binary tree to doubly linked list, 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 binary tree to doubly linked list, then convert right sub binary 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 binary tree to doubly linked list with zigzag order traversal of tree.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
struct queue{
    struct node *element;
    struct queue *next;
};
typedef struct queue Queue;
 
void enqueue(Queue **queue, Node *node){
	Queue *q  = NULL;
	Queue *head  = *queue;
 
	if(*queue == NULL){
		//This is the first node in the queue
		q =(Queue *)malloc(sizeof(Queue));
		q->element = node;
		q->next = NULL;
		*queue = q;
	}
	else{
		q = *queue;
		//Get to the last node, can be optimized by keeping 
                //the last pointer.
		while(q->next)
			q = q->next;
 
		Queue *newNode =(Queue *)malloc(sizeof(Queue));
		q->next = newNode;
		newNode->element = node;
		newNode->next = NULL;
		*queue = head;
	}
}
int isEmpty( Queue *queue){
	if(queue != NULL)
	    return 0;
 
	return 1;
}
Node * front(Queue *queue){
	if(!isEmpty(queue))
	     return queue->element;
 
	return NULL;
}
 
void dequeue(Queue **queue){
	Queue *q = *queue;
 
	Queue *currentNode = q;
	q = currentNode->next;
	currentNode = NULL;
	free(currentNode);
	*queue = q;
}
 
Node * createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
	return newNode;
}
 
Node * addNode(Node *node, int value){
	if(!node) return createNode(value);

	if (node->value > value)
	    node->left = addNode(node->left, value);
	else
	    node->right = addNode(node->right, value);

	return node;
}
 
void treeToList(Node *root, Node **headPointer){
 
	Queue *queue = NULL;
	Node * last = NULL;
 
	//If tree is null to start with, return
	if(!root)
		return ;
 
	//If there is a node, enqueue the first node
	enqueue(&queue, root);
 
	//Now, till the time there is a node in queue, repeat
	while(!isEmpty(queue)){
		/* Take the first element and put both left and 
                right child on queue */
		Node * currentNode = front(queue);
		printf("Dequeue : %d\n", currentNode->value );
		if(currentNode->left)
			enqueue(&queue, currentNode->left);
		if(currentNode->right)
			enqueue(&queue, currentNode->right);
 
		//If last node is not null, it's right must 
                //point to current node.
		if(last)
			last->right = currentNode;
        else{
        	*headPointer = currentNode; 
        }
 
        //Current node's left should point to last node we processed. 
        currentNode->left = last;
        //Update the last node to current Node.
        last = currentNode;
 
        //Take the node out of queue.
        dequeue(&queue);
	}
 
} 
/* Driver program for the function written above */
int main(){
        Node *root = NULL;
        Node * head = NULL;

       //Creating a binary tree
        root = addNode(root,30);
        root = addNode(root,20);
        root = addNode(root,15);
        root = addNode(root,25);
        root = addNode(root,40);
        root = addNode(root,37);
        root = addNode(root,45);
 
        treeToList(root,&head);
 
        Node *current = head;
        while(current){
            printf("%d ", current->value);
            current = current->right;
        }
 
        return 0;
}

Please leave a comment if you feel there is some mistake or there is another efficient way to do this. Follow us for more such coding problems and videos. If you want to contribute to website, please contact us and earn money too!

  • http://www.blogger.com/profile/08696495591002716947 A.Vamshi Krishna

    /* If this wasn’t the first node being added to list*/
    if(*last != NULL){
    (*last)->right = node;
    }

    we need add logic to set ptrToHead

    if(*last != NULL){
    (*last)->right = node;
    }else {
    *ptrToHead=node;
    }

  • http://www.blogger.com/profile/07885594236543253450 Jitendra Sangar

    Agreed, will correct the code.

  • http://kaushik-lele-algos-datastructures.blogspot.in/ kaushik Lele

    Please change this sentense —>
    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.

    It is written opposite. It should be
    “right” pointer of the last node …
    “left” pointer of current node …

    In code it is done correctly but mismatch in explanation

    • http://algorithmsandme.in/ Jitendra Sangar

      Thanks a lot for pointing out. Will correct it.

  • Piyush Shandilya

    The code works fine for a pouplated tree. However if I run call treeTolist(root) after every insertion, i.e. for an on-the-fly insertion in BST, the code give a StackOverFlowError.

    • http://algorithmsandme.com/ Jitendra Sangar

      Can you please share the code which is giving SO. You can share the Ideone.com link. Thanks