Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
What is a Doubly Linked List?
3.
Sample Example
4.
Approach 1: Reverse Inorder traversal
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in C++
4.4.
Complexities
5.
Approach 2: Inorder traversal
5.1.
Algorithm
5.2.
Dry Run
5.3.
Implementation in C++
5.4.
Complexities
6.
Frequently Asked Questions
6.1.
What is a doubly linked list?
6.2.
Is it possible to convert a doubly linked list back to a binary tree?
6.3.
What are the advantages of using a doubly linked list over a singly linked list?
6.4.
What is the difference between a binary tree and a binary search tree?
6.5.
Are these problems asked in coding interviews?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Binary Tree to Doubly Linked List

Introduction

Binary Tree is a data structure where data is stored in a node, and each node has either two child nodes, one child node, or no child node. The three primary traversal techniques are preorder, inorder, and postorder.

A linked List is another type of data structure where data is stored in nodes, and each node is connected via links. A linked list can be singly linked or doubly linked, depending upon the number of links. There are two pointers in a doubly-linked list: next and previous. 

introduction image

In this blog will discuss the problem of converting a given binary tree into a doubly linked list by performing reverse inorder and inorder traversal. To know more about the various tree traversals, click here Tree Traversals.

Problem Statement

Convert a binary tree with nodes into a doubly-linked list.

What is a Doubly Linked List?

A doubly linked list is a data structure that consists of a collection of nodes, where each node contains a value and references to both the next and previous nodes in the list. This allows for efficient traversal in both directions (i.e., forwards and backwards) through the list, as well as insertion and deletion of elements at any position. The first and last nodes typically have a null reference for the next and previous nodes, respectively.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Sample Example

Input

image of binary tree

Output

image of doubly linked list

Recommended: try to solve the problem first on our Coding Ninjas Studio by clicking here Convert A Given Binary Tree To a Doubly Linked List

Approach 1: Reverse Inorder traversal

Here in this approach, we will be creating a new Doubly linked list. We will use the reverse inorder traversal. If we do the inorder traversal, the linked list obtained would be reversed, so to avoid that, we will traverse the Tree using reverse inorder, i.e., visit the right subtree and, after that, visit the root and, in the end, visit the left subtree.

Algorithm

  1. The base case of our recursion is that if the root is null, we return and end the recursion. 
  2. We call the right sub-tree first and set its value to the head of our linked list. 
  3. We then check if the head is null or not. If it is not null, then the left side of the head contains the root
  4. After assigning the root value in the head, we traverse the left sub-tree.
  5. Like this Tree will be traversed recursively.

Dry Run

Now let us see the dry run of the sample example,

image of binary tree

Now, doing the reverse inorder traversal of the above tree,

Order of reverse inorder traversal:  Right → Root → Left

Step-1

First, we will visit the right subtree, and in the right subtree, we will visit the right node of the right subtree, i.e., 19. This node will become the tail of the doubly linked list.

step-1 image

Step-2

Now visiting the root of the right subtree i.e., 8.

step-2 image

Step-3 

Similarly, visiting the left node of the right subtree, i.e., 18.

step-3 image

Step-4

Now since the right subtree is over, the root of the Tree, i.e., 4, will be visited,

step-4 image

Step-5

After visiting the root, the left subtree will be visited now, in the left subtree right node of the root of the left subtree i.e., 10, will be visited first,

step-5 image

Step-6

Visiting the root of the left subtree, i.e., 3,

step-6 image

Step-7

In the end, we will visit the left node of the left subtree, i.e., 9, 

step-7 image

 

So the final doubly linked list will look like this:

image of final doubly linked list

Now let us look at the implementation of the above approach in C++.

Implementation in C++

#include <iostream>
#include <queue>
using namespace std;

// class to represent the binary tree
class Tree
{
public:
    int data;
    Tree *left;
    Tree *right;

    Tree(int value)
    {
        data = value;
        left = right = NULL;
    }
};

// class to convert the binary tree to a doubly linked list
class BTreeDLL
{
    // root of the binary tree
    Tree *root;

    // head of the doubly linked list
    Tree *head = NULL;

public:
    void createDLL(Tree *root)
    {
        // if root is null then return
        if (root == NULL)
            return;

        // call for the right subtree
        createDLL(root->right);

        // set the value of right subtree to head of the list
        root->right = head;

        // if the list is not empty
        if (head != NULL)
            // then insert the node at the beginning
            head->left = root;
        // else intialize the head of the list
        head = root;

        // call for the left subtree
        createDLL(root->left);
    }

    // function to print the doubly linked list
    void printTree(Tree *head)
    {
        while (head != NULL)
        {
            cout << head->data << " ";
            head = head->right;
        }
    }

    // function to print the binary tree (Level order traversal)
    void printBT(Tree *root)
    {
        if (root == NULL)
            return;
        queue<Tree *> q;

        // insert the root in the queue
        q.push(root);
        while (!q.empty())
        {
            int nC = q.size();
            // printing nodes by every level of the binary tree
            while (nC > 0)
            {
                Tree *node = q.front();
                cout << node->data << " ";
                q.pop();

                // if left child exists then push the left child in the queue
                if (node->left != NULL)
                    q.push(node->left);

                // if right child exists then push the right child in the queue
                if (node->right != NULL)
                    q.push(node->right);

                nC--;
            }
            cout << endl;
        }
    }

    void test()
    {
        // creating a new binary tree
        root = new Tree(4);
        root->left = new Tree(3);
        root->right = new Tree(8);
        root->left->left = new Tree(9);
        root->left->right = new Tree(10);
        root->right->left = new Tree(18);
        root->right->right = new Tree(19);

        cout << "The Binary Tree is:" << endl;
        printBT(root);

        createDLL(root);

        cout << "The Linked List Formed: ";
        printTree(head);
    }
};

int main()
{
    BTreeDLL tree;
    // calling the test function of the BTreeDLL class
    tree.test();
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output

The Binary Tree is:
4
3 8
9 10 18 19
The Linked List Formed: 9 3 10 4 18 8 19
You can also try this code with Online C++ Compiler
Run Code

Complexities

Time Complexity

Since we are traversing the binary tree of n nodes once to create our doubly linked list. Thus time complexity O(n), where n is the number of nodes.

Space Complexity

Since we are using recursion to make our doubly linked list in the given implementation. Thus, space complexity would be O(h), where h is the size of the recursion stack.

Approach 2: Inorder traversal

Another approach to convert a binary tree to a doubly linked list is to perform an inorder traversal of the Tree. Inorder, traversal visits the left subtree, the root, and then the right subtree. By maintaining a pointer to the previous node visited during the traversal, we can create the doubly linked list by linking the previous node's right pointer to the current node and the current node's left pointer to the previous node.

Algorithm

  1. First, create a pointer named prev to store the previous node's address.
  2. The base case of our recursion is that if the root is null, we return and end the recursion. 
  3. Else we call the left subtree first.
  4. If prev is null, then initialize the head of the list.
  5. Else the left side of the root will point to the prev pointer, and the right side of the prev pointer will point to the root. 
  6. Update the value of the previous pointer to the root.
  7. Now we will traverse the right subtree recursively.
  8. Like this Tree will be traversed recursively.

Dry Run

Now let us see the dry run of the sample example,

image of binary tree

Now, doing the reverse inorder traversal of the above tree,

Order of reverse inorder traversal:  Left→ Root → Right

Step-1

First, we will visit the left subtree, and in the left subtree, we will visit the left node first, i.e., 9. This node will become the head of the doubly linked list.

step-1 image

Step-2

Now visiting the root of the left subtree i.e., 3.

step-2 image

Step-3 

Similarly, visiting the right node of the left subtree, i.e., 10.

step-3 image

Step-4

Now since the left subtree is over, the root of the Tree, i.e., 4, will be visited,

step-4 image

Step-5

After visiting the root, the right subtree will be visited now, in the right subtree the left node i.e., 10, will be visited first,

step-5 image

Step-6

Visiting the root of the right subtree, i.e., 8,

step-6 image

Step-7

In the end, we will visit the right node of the right subtree, i.e., 19, 

step-7 image

 

So the final doubly linked list will look like this:

final doubly linked list image

 

Now let us look at the implementation of the above approach in C++.

Implementation in C++

#include <iostream>
#include <queue>
using namespace std;

// class to represent the binary tree
class Tree
{
public:
    int data;
    Tree *left;
    Tree *right;

    Tree(int value)
    {
        data = value;
        left = right = NULL;
    }
};

// class to convert the binary tree to doubly linked list
class BTreeDLL
{
    // root of the binary tree
    Tree *root;

    // previous node
    Tree *prev = NULL;

    // head of the doubly linked list
    Tree *head = NULL;

public:
    void createDLL(Tree *root)
    {
        // if root is null then return
        if (root == NULL)
            return;

        // call for the left subtree
        createDLL(root->left);

        // if previous is null then initialize the head of the list
        if (prev == NULL)
            head = root;
        else
        {
            // set the root's left child to prev
            root->left = prev;

            // set the previous node's right child to root
            prev->right = root;
        }

        // update the previous
        prev = root;

        // call for the right subtree
        createDLL(root->right);
    }

    // function to print the doubly linked list
    void printTree(Tree *head)
    {
        while (head != NULL)
        {
            cout << head->data << " ";
            head = head->right;
        }
    }

    // function to print the binary tree (Level order traversal)
    void printBT(Tree *root)
    {
        if (root == NULL)
            return;
        queue<Tree *> q;

        // insert the root in the queue
        q.push(root);
        while (!q.empty())
        {
            int nC = q.size();
            // printing nodes by every level of the binary tree
            while (nC > 0)
            {
                Tree *node = q.front();
                cout << node->data << " ";
                q.pop();

                // if left child exists then push the left child in the queue
                if (node->left != NULL)
                    q.push(node->left);

                // if right child exists then push the right child in the queue
                if (node->right != NULL)
                    q.push(node->right);

                nC--;
            }
            cout << endl;
        }
    }

    void test()
    {
        // creating a new binary tree
        root = new Tree(4);
        root->left = new Tree(3);
        root->right = new Tree(8);
        root->left->left = new Tree(9);
        root->left->right = new Tree(10);
        root->right->left = new Tree(18);
        root->right->right = new Tree(19);

        cout << "The Binary Tree is:" << endl;
        printBT(root);

        createDLL(root);

        cout << "The Linked List Formed: ";
        printTree(head);
    }
};

int main()
{
    BTreeDLL tree;
    // calling the test function of the BTreeDLL class
    tree.test();
    return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output

The Binary Tree is:
4
3 8
9 10 18 19
The Linked List Formed: 9 3 10 4 18 8 19

Complexities

Time Complexity

Since we are traversing the binary tree of n nodes once to create our doubly linked list. Thus the time complexity is O(n), where n is the number of nodes.

Space Complexity

Since we are using recursion to make our doubly linked list in the given implementation. Thus, space complexity would be O(h), where h is the size of the recursion stack.

Frequently Asked Questions

What is a doubly linked list?

A doubly linked list is a data structure that consists of a sequence of nodes, where each node has a reference to the previous node and the next node in the sequence. This allows for efficient traversal in both directions, unlike a singly linked list where only forward traversal is possible.

Is it possible to convert a doubly linked list back to a binary tree?

Yes, it is possible to convert a doubly linked list back to a binary tree, but it requires additional information about the structure of the original tree, such as the depth or in-order traversal of the nodes.

What are the advantages of using a doubly linked list over a singly linked list?

A doubly linked list allows for efficient traversal in both directions, whereas a singly linked list only allows for forward traversal. Doubly linked lists also allow for efficient insertion and deletion of elements at both ends of the list.

What is the difference between a binary tree and a binary search tree?

A binary search tree is a specific type of binary tree where the left child node has a value less than the parent node, and the right child node has a value greater than the parent node. This allows for efficient searching and insertion of elements in the tree.

Are these problems asked in coding interviews?

Yes, such questions are asked in the coding interviews of various companies like Adobe, Facebook, Google, and Amazon. 

Conclusion

In a nutshell, this article discussed the conversion of a binary tree to a doubly-linked list thoroughly. We saw the problem statement, an example, an approach to the problem, its Java implementation, and the time and space complexities. We concluded the article with a few questions asked in interviews.

Recommended Problems -

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.
Learn various topics from Web Technologies, Programming Fundamentals, Data Structures, and Algorithms from our Library.

Happy Learning!!

Live masterclass