Convert a given Binary Tree to Doubly Linked List

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a binary tree. We have to convert the given binary tree to a doubly-linked list.

Problem Statement Understanding

We have to store the inorder traversal of the given binary tree in the newly created linked list.

Sample Input:

Sample Output:

Explanation:

The output doubly linked list contains the in-order traversal of the given binary tree.

We should note that the order of the nodes in the doubly linked list must be the same as the in-order traversal of the binary tree. The first node of the in-order traversal must be the head of the doubly linked list. The left and right pointers will be used as previous and next pointers, respectively. Let us have a glance at the approach.

Approach#1

In this approach, we will traverse do an inorder traversal of the binary tree. We will add the nodes at the beginning of the newly created linked list, and update the head every time. But there is a problem. Since we will insert at beginning, the order or the linked list that we will recieve, will be reversed.

To correct that, we can do a reverse inorder traversal of the tree, i.e. we will traverse through the right subtree before the left subtree.

Algorithm

  • Base Case - If the root is NULL, then simply return.
  • Recur for the right subtree.
  • Make the current root’s right point to head, and head’s left pointer to the the current root. By doing this, we are adding the current root to the head , and make the current root the head.
  • After the above step, recur for the left subtree.
  • Recursively, the tree will be traversed and the doubly linked list will be created as discussed.

Dry run

Code Implementation

#include 

struct Node {
    int data;
    Node *left, *right;
};

Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
void BToDLL(Node* root, Node*& head)
{
 
    if (root == NULL)
        return;

    BToDLL(root->right, head);

    root->right = head;

    if (head != NULL)
        head->left = root;

    head = root;

    BToDLL(root->left, head);
}

void printList(Node* head)
{
    printf("Extracted Doubly Linked list is:\n");
    while (head) {
        printf("%d ", head->data);
        head = head->right;
    }
}

int main()
{

    Node* root = newNode(11);
    root->left = newNode(12);
    root->right = newNode(15);
    root->left->left = newNode(20);
    root->left->right = newNode(30);
    root->right->left = newNode(36);

 
    Node* head = NULL;
    BToDLL(root, head);
 
    printList(head);
 
    return 0;
}
class Node {
    int data;
    Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
public class BinaryTree {

    Node root;
 

    Node head;
 

    void BToDLL(Node root)
    {

        if (root == null)
            return;
 

        BToDLL(root.right);
 

        root.right = head;
 

        if (head != null)
            head.left = root;
 

        head = root;
 

        BToDLL(root.left);
    }

    void printList(Node head)
    {
        System.out.println("Extracted Doubly Linked List is : ");
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.right;
        }
    }

    public static void main(String[] args)
    {

        BinaryTree tree = new BinaryTree();
        tree.root = new Node(11);
        tree.root.left = new Node(12);
        tree.root.right = new Node(15);
        tree.root.left.left = new Node(20);
        tree.root.left.right = new Node(30);
        tree.root.right.left = new Node(36);
        
        tree.BToDLL(tree.root);
        tree.printList(tree.head);
    }
}

Output :

Extracted Doubly Linked list is:
20 12 30 11 36 15

Time Complexity: O(N), as tree traversal is needed.

Space Complexity: O(N), for the recursion stack and the doubly linked list.

Now, let us have a look at another approach. The time complexities of both the approaches are the same.

Approach#2

The approach is going to be pretty simple. We will do the in-order traversal of the given tree, and one by one, change the links of each node that we encounter. The doubly linked list will be created In-Place. Let us have a look at the algorithm to get a clearer look.

Algorithm

  • Base Case - If the root is NULL, return NULL.
  • Create a node prev and initialize with NULL.
  • Recur for the left subtree.
  • Now, if prev is NULL, then the root will be the head of our doubly linked list.
  • Else, the left of the root will point to prev and the right of prev will point to the root.
  • After the above conditional statements, change the value of prev to root.
  • In the end, recur for the right subtree.

Code Implementation

#include 
using namespace std;
 

struct node
{
    int data;
    node* left;
    node* right;
};
 

void BinaryTree2DoubleLinkedList(node *root, node **head)
{
    // Base Case
    if (root == NULL) return;
 
    // Create a prev node
    static node* prev = NULL;

    // Recur for left subtree
    BinaryTree2DoubleLinkedList(root->left, head);

    // Make the leftmost element the head ofr DLL
    if (prev == NULL)
        *head = root;
    else
    {
        // Change links 
        root->left = prev;
        prev->right = root;
    }
    // Change the value of prev to root
    prev = root;
 
    BinaryTree2DoubleLinkedList(root->right, head);
}

node* newNode(int data)
{
    node* new_node = new node;
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return (new_node);
}
 
void printList(node *node)
{
    while (node!=NULL)
    {
        cout << node->data << " ";
        node = node->right;
    
}
 
int main()
{
    
    node *root        = newNode(11);
    root->left        = newNode(12);
    root->right       = newNode(15);
    root->left->left  = newNode(20);
    root->left->right = newNode(30);
    root->right->left = newNode(36);
 
 
    node *head = NULL;
    BinaryTree2DoubleLinkedList(root, &head);

    printList(head);
 
    return 0;
}
class Node
{
    int data;
    Node left, right;

    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}

public class BinaryTree
{
    Node root;

    Node head;

    static Node prev = null;

    void BinaryTree2DoubleLinkedList(Node root)
    {

        if (root == null)
            return;

        BinaryTree2DoubleLinkedList(root.left);


        if (prev == null)
            head = root;
        else
        {
            root.left = prev;
            prev.right = root;
        }
        prev = root;

        BinaryTree2DoubleLinkedList(root.right);
    }

    void printList(Node node)
    {
        while (node != null)
        {
            System.out.print(node.data + " ");
            node = node.right;
        }
    }

    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(11);
        tree.root.left = new Node(12);
        tree.root.right = new Node(15);
        tree.root.left.left = new Node(20);
        tree.root.left.right = new Node(30);
        tree.root.right.left = new Node(36);

        tree.BinaryTree2DoubleLinkedList(tree.root);

        tree.printList(tree.head);

    }
}

Output:

20 12 30 11 36 15

Time Complexity: O(N), as a simple in-order traversal is needed.

Space Complexity: O(N), the space required for recursion stack.

So, in this article, we have tried to explain the most efficient approach to covert a binary tree to a doubly-linked list. This is a very important problem when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Iterative Selection Sort For Linked List
Next post Create Linked List From A Given Array

Leave a Reply

Your email address will not be published. Required fields are marked *