  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Convert a given Binary Tree To Doubly Linked List | Set 3

Last Updated on December 14, 2022 by Prepbytes ### Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

### Problem Statement

In this problem, we are given a binary tree, and we have to convert it to a doubly linked list.

### Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Let’s assume that the given binary tree is: • According to the problem statement, we need to convert this given binary tree to a doubly linked list.
• After converting the given tree to a doubly linked list, our doubly linked list will look like: Taking another example, if the given binary tree is: • Then, in this case, our doubly linked list will be: Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Before moving on further, let’s see some helpful observations, which will help us to approach this problem.

Let’s name every node to check its relative position in the binary tree and doubly linked list. In the binary tree, we can observe that:

• The root node is A, which has B as its left child and C as its right child.
• B has D as its left child and E as its right child.
• C has F as its left child and G as its right child.

In the converted doubly linked list, we can observe that:

• Node B has D as its previous node, which was its left child in the binary tree, and E as its next node, which was its right child in the binary tree.
• Node C has F as its previous node, which was its left child in the binary tree, and G as its next node, which was its right child in the binary tree.

So, from the above observations, you might think that we can just make the previous pointer of a node point to its left child and the next pointer point to its right child.

• Yes, that is partially true because, as you can see the node A has B as its left child, but its previous pointer is pointing to E in the doubly linked list.

Another observation here is that all the nodes in the left subtree rooted at a node lie on the left side of the node in the list. Similarly, all the nodes in the right subtree rooted at a node lie on the right side of the node in the list.

• We can achieve this using inorder traversal of the tree.

Inorder order traversal: In inorder traversal, we first visit the left subtree, then the root, and then right subtree: If we do the inorder traversal of the given above given tree, we will get:
7 2 8 0 9 3 10

On careful observation, you can see, the values are in the same order as in our output list.

So, the key takeaways are:

• The left child can only be replaced with the previous node and the right child with the next node.
• The nodes of the doubly linked list should follow the same order as the inorder traversal of the tree.

### Approach

• From the above observations, it is clear that the list will have nodes in the same order as the inorder traversal of the tree. So, we first convert the left subtree to a doubly linked list and append the resultant list to the final list and then append the root node to the final list and then convert the right subtree to a doubly linked list and append the resultant list to the final list.
• Now the question arises, how do we convert the left subtree or the right subtree to a doubly linked list. And the answer is recursion.
• A subtree follows all the properties of the parent tree. So this problem is similar to the original problem. We treat the left child of the root as the new root and convert the subtree rooted at the left child (left child of the left child of the original root) of the new root (left child of the original root) and then convert the new root and then the subtree rooted at the right child of the new root.
• We perform this operation recursively until the problem becomes trivial to solve. By trivial problem, I mean converting a binary tree that has at most three nodes, a root, left child, and right child. This problem can be solved easily as we just first append the left child to the list, then the root, and then the right child.
• To append a node to the list, we just need to make the next pointer of the head node point to the node, and make the previous pointer of this node point to the head.

### Algorithm

To convert the given binary tree to a doubly linked list, we need to do an inorder traversal of the binary tree.

• Create a node Head, which will act as the starting node of our doubly linked list.
• Create a method convertToDoubleLinkedList(), which is called recursively, to perform inorder traversal on the binary tree and convert it to a doubly linked list.
• Call method convertToDoubleLinkedList() on the root.
• If the root is null, that means the tree rooted at this root does not exist. So, we simply return.
• Call the method convertToDoubleLinkedList() on the left child of the root node (the node which is passed to the convertToDoubleLinkedList method). This will convert the left subtree rooted at the root node by recursively calling all the subtrees rooted at the root.left as well as root.right and append the list to the final output list.
• As the left subtree is already converted to the list, append the root node to the list.
• Call the method convertToDoubleLinkedList() on the right child of the root node (the node which is passed to the convertToDoubleLinkedList method). This will convert the right subtree rooted at the root node by recursively calling all the subtrees rooted at the root.left as well as root.right and append the list to the final output list.
• Now, print the final list.

### Dry Run   ### Code Implementation

```#include <stdio.h>
#include<stdlib.h>

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

// A simple recursive function to convert a given Binary tree to Doubly
// root --> Root of Binary Tree
{
// Base case
if (root == NULL) return;

// Initialize previously visited node as NULL. This is
// static so that the same value is accessible in all recursive
// calls
static struct node* prev = NULL;

// Recursively convert left subtree

// Now convert this node
if (prev == NULL)
else
{
root->left = prev;
prev->right = root;
}
prev = root;

// Finally convert right subtree
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->left = new_node->right = NULL;
return (new_node);
}

/* Function to print nodes in a given doubly linked list */
void printList(struct node *node)
{
while (node!=NULL)
{
printf("%d ",node->data);
node = node->right;
}
}

/* Driver program to test above functions*/
int main()
{
// Let us create the tree shown in above diagram
struct node *root        = newNode(10);
root->left        = newNode(12);
root->right       = newNode(15);
root->left->left  = newNode(25);
root->left->right = newNode(30);
root->right->left = newNode(36);

// Convert to DLL

// Print the converted list

return 0;
}
```
```#include <iostream>
using namespace std;

/* A binary tree node has data, and left and right pointers */
struct node
{
int data;
node* left;
node* right;
};

// A simple recursive function to convert a given Binary tree to Doubly
// root --> Root of Binary Tree
{
// Base case
if (root == NULL) return;

// Initialize previously visited node as NULL. This is
// static so that the same value is accessible in all recursive
// calls
static node* prev = NULL;

// Recursively convert left subtree

// Now convert this node
if (prev == NULL)
else
{
root->left = prev;
prev->right = root;
}
prev = root;

// Finally convert right subtree
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
node* new_node = new node;
new_node->data = data;
new_node->left = new_node->right = NULL;
return (new_node);
}

/* Function to print nodes in a given doubly linked list */
void printList(node *node)
{
while (node!=NULL)
{
cout << node->data << " ";
node = node->right;
}
}

/* Driver program to test above functions*/
int main()
{
// Let us create the tree shown in above diagram
node *root        = newNode(10);
root->left        = newNode(12);
root->right       = newNode(15);
root->left->left  = newNode(25);
root->left->right = newNode(30);
root->right->left = newNode(36);

// Convert to DLL

// Print the converted list

return 0;
}
```
```public class Prepbytes
{
// Structure of a tree node
static class Node
{
int data;
Node left = null;
Node right = null;

Node(int data) {
this.data = data;
}
}

static Node prev = null;

// Using this function we will be converting a tree rooted at this node to a doubly linked list.
{
if (root == null)
return;

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

}

// Using this function we will be printing the Doubly Linked List.
{
while (curr != null)
{
System.out.print(curr.data + " ");
curr = curr.right;
}
}

public static void main(String[] args)
{
Node root = new Node(0);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(7);
root.left.right = new Node(8);
root.right.left = new Node(9);
root.right.right = new Node(10);

}
}
```
```class Node:
def __init__(self, data):
self.right = None
self.data = data
self.left = None

class BtoDll:
def __init__(self):
self.tail = None

def convert(self, root):

if root is None:
return

self.convert(root.left)

node = root
else:
self.tail.right = node
node.left = self.tail
self.tail = node

self.convert(root.right)

converter = BtoDll()
return converter.convert(root)

if __name__ == "__main__":

root = Node(0)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.right = Node(8)
root.right.left = Node(9)
root.right.right = Node(10)

```