Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

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.

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

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

The base case of our recursion is that if the root is null, we return and end the recursion.

We call the right sub-tree first and set its value to the head of our linked list.

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.

After assigning the root value in the head, we traverse the left sub-tree.

Like this Tree will be traversed recursively.

Dry Run

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

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

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

Step-3

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

Step-4

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

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

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

Step-7

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

So the final doubly linked list will look like this:

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

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

First, create a pointer named prev to store the previous node's address.

The base case of our recursion is that if the root is null, we return and end the recursion.

Else we call the left subtree first.

If prev is null, then initialize the head of the list.

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.

Update the value of the previous pointer to the root.

Now we will traverse the right subtree recursively.

Like this Tree will be traversed recursively.

Dry Run

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

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

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

Step-3

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

Step-4

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

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

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

Step-7

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

So the final doubly linked list will look like this:

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

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.

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.