Binary tree to doubly linked list conversion

Tags: , , , ,

Binary tree to doubly linked list conversion

This is very commonly asked problem in Amazon and Google interview question. It checks your understanding of binary tree and doubly link list data structures, their traversals and creation. In a binary tree, a node has two pointers, one point to the left child of the node and other points to the right child of the node. Similarly, in a doubly linked list, a node contains two pointers, one point to the next node and other points to the previous node of the current node. Given a binary tree, how can we convert the binary tree to a doubly linked list? To make the problem clear, let’s take an example.

convert binary tree to dll
Binary tree to doubly linked list conversion

Output should be

convert binary tree to doubly linked list
Doubly linked list from binary tree

Binary tree to a doubly linked list: Line of thought

The first question you should be asking is which node should be the head of the doubly linked list? If the leftmost node in the binary tree is to be head, you need to traverse a tree in inorder. However, if the root node has to be the head node, then you should do preorder traversal.

This question could be great started as it shows your understanding of tree traversals.

Let’s say our problem is to have inorder traversal. If a binary tree is binary search tree, the interviewer can just tell you to provide the output as a sorted list, which is another way of saying inorder traversal.

To convert a binary tree to a doubly linked list, at each node, the previous pointer will point to the inorder predecessor of the node whereas next pointer points to inorder successor of the node. We have left and right pointers already in the node, use them as previous and next pointer respectively.
Now, problem is to keep track of inorder successor and predecessor of the node. To keep track of inorder predecessor, store the previous node of the current node visited throughout traversal. We would link the left child to the inorder predecessor.
How to keep find the inorder successor of a node, if the node is left child of some node, the inorder successor would be parent node. At the parent node, it would be the leftmost child of the right child if it exists. This is not scary as it sound, inorder successor part is automatically implemented if we do the recursive inorder traversal of the tree.

There is one special case to handle, which is the leftmost node. This node will be head of the doubly linked list and there is no previous node to link it’s left to. 

This whole problem is a complex version of inorder traversal of a binary tree, but at the end, it is inorder traversal. We can first write the generic inorder traversal and then modify the process step to suit our needs.

    private void inorder(Node root){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        process(root);
        if(root.right != null) inorder(root.right);
    }

We have to modify this to send previous node, where root connects it’s left child in process step and head, which is set only once, to store the head of result doubly linked list.

private void inorder(Node root, Node prev, Node head){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        process(root, prev,head);
        if(root.right != null) inorder(root.right);
    }

What we have to do in process step? If the current node is the leftmost node, we will set that head of the doubly linked list. If the previous node is null yet, that means, we have it the leftmost node.
What if the previous node is not null, in that case, we have already created or assigned head of the doubly linked list, and the previous node points to the last node of the doubly linked list. It means we have to link right pointer of the previous node to the current node.
Set left pointer of the current node to the previous node irrespective of the previous node. The last step would update the previous with the current node.

private void process(TreeNode root, TreeNode prev, TreeNode head){
	if(prev == null){
		head = root;
	}
	else{
		prev.setRight(root);
	}
	root.setLeft(prev);
	prev = root;
}

The only problem is that if we are implementing the process function Java, we cannot change the value of pointer because Java passes arguments as pass-by-value rather than pass-by-reference. In short, even though head and previous pointers are updated in process function, the change would not be reflected in the calling function. To handle this, we will create a mutable static class with two members called head and previous and pass it to process function. Why this method works, please refer  :  pass-by-value and pass-by-reference in java

    private void process(TreeNode root, Context context){
        if(context.prev == null){
            context.head = root;
        }
        else{
            context.prev.setRight(root);
        }

        root.setLeft(context.prev);
        context.prev = root;
    }

An algorithm to convert a binary tree to a doubly linked list

  1. Start from root node, currentNode.
  2. If currentNode->left != NULL, currentNode = currentNode->left. (Moving down the tree on the left side)
  3. At this point we are at the left most node, check if previous == NULL.
    1. If previous is NULL, then this node has to be the head node.
    2. Mark currentNode as head and currentNode->left = previous = NULL.
  4. previous = currentNode.
  5. Traverse up the tree in inorder traversal.
    1. previous->right = currentNode.
    2. currentNode->left = previous
    3. previous = currentNode
  6. If currentNode->right != NULL, currentNode = currentNode->right and go to step 2.

Convert Tree to DLL : implementation in Java

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeToDLL {

    public static class Context {
        public TreeNode head;
        public TreeNode prev;
    }
    
    private void process(TreeNode root, Context context){
        if(context.prev == null){
            context.head = root;
        }
        else{
            context.prev.setRight(root);
        }

        root.setLeft(context.prev);
        context.prev = root;
    }

    public void treeToDllRecursion(TreeNode root, Context context){

        if(root == null) return;

        if(root.getLeft() != null) {
            treeToDllRecursion(root.getLeft(),context);
        }

        process(root,context);

        if(root.getRight() != null)
			treeToDllRecursion(root.getRight(), context);
    }
}

Definition of TreeNode and BinarySearchTree is given below.

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}
package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree<T> {

    private TreeNode<T> root;

    public void BinarySearchTree(){
        root = null;
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private TreeNode insertNode(TreeNode root, int value){
        if(root == null){
            //if this node is root of tree
            root = new TreeNode(value);
        }
        else{
            if((int)root.getValue() > value){
                /*If root is greater than value,
				node should be added to left subtree */
                root.setLeft(insertNode(root.getLeft(), value));
            }
            else{
                /*If root is less than value,
				node should be added to right subtree */
                root.setRight(insertNode(root.getRight(), value));
            }
        }
        return root;
    }
    
    public TreeNode getRoot(){
        return this.root;
    }

    public void setRoot(TreeNode node){
        this.root = node;
    }
  }

Binary search tree to DLL conversion : 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 ** prev, Node **ptrToHead){
        if(node == NULL)
                return;
        /* Go to left most child */
        if(node->left)
                treetoListRec(node->left, prev, ptrToHead);

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

        node->left = *prev;
        *prev= node;

        /* If there is right child, process right child */
        if(node->right)
                treetoListRec(node->right, prev, 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 create_node(value);
    else{
        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 * prev = 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,&prev, &ptrToHead);
        
        return 0;
}

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 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

Please share if there is something missing or wrong. If you want to contribute to website, please reach out to us on communications@algorithmsandme.com