## Problem Statement

Given a Binary Tree convert it into a Doubly Linked List (DLL) where the left and right pointers are modified to the previous and next pointers of the resultant Doubly linked list. The order of nodes in the doubly linked list should be the same as the order of the nodes in the Inorder traversal of the binary tree. Therefore the first node(head) of a doubly linked list will be the leftmost node of the binary tree since we are following Inorder traversal.

## Example

For a better understanding of the problem statement, let’s look at the below example:

**Input:**

Consider the input binary tree shown in the below image:

**Output:**

```
18 45 9 40 6 14 12
```

The doubly linked list formed is shown in the below image:

## Example Explanation

We can observe that the order of the doubly linked list is the same as the Inorder traversal on the given binary tree. Therefore the nodes of the modified doubly linked list are printed as the output.

## Input Format

During competitive programming, the input of the binary tree is given by indicating the value of the data field in each node by providing the root of the binary tree.

## Output Format

The output includes printing the node’s values of the newly formed Doubly linked list. Print all the nodes in the doubly linked list.

## Constraints

- 1<=
*N*(Number of nodes in the binary tree) <=10^{5} - Value in the data field can be any real number.

## Approach 1: By Processing Subtrees

We need to convert the given binary tree to a doubly linked list **in place**, which means no extra space is needed. So the basic approach can be just manipulating the left and right pointer of the node to the next and previous pointers as in a doubly linked list. We can process the left subtree first and get the head of the doubly linked list, which is the leftmost node in the given binary tree. And by processing the right subtree we get the nodes that are to the right side of the root in the doubly linked list. Using the **Inorder predecessor** of the root in the left subtree which is considered to be the rightmost node in the left subtree and helps in attaching with the leftmost node of the right subtree and forming a DLL. And also using the **Inorder successor** of the root in the right subtree which is the leftmost node in the right subtree. The basic idea is to use **recursion**, to recursively convert each subtree into a doubly linked list.

### Algorithm

The below algorithm clearly explains the approach for converting the given binary tree to a doubly linked list:

- Here, the idea is the left subtree is processed first and right subtree is processes next as in the
**Inorder traversal** **Check whether the left subtree exists**, if it exists then follow the below three steps to convert the left subtree of the root to the doubly linked list:**Recursively**call the left subtree to convert it into a doubly linked list.- For every call
**find the Inorder predecessor of the root in the left subtree**which is considered to be the next element in the doubly linked list formed. - After finding the Inorder predecessor, name it as the previous node and now root is the next of the previous node (i.e next of the Inorder predecessor).

- Similarly for the right subtree,
**if the right subtree exists**for the root. Follow the below steps if the right subtree of the root node exists:**Recursively**call the right subtree to convert it into a doubly linked list.- For every recursive call on the right subtree,
**find the Inorder successor of the root in the right subtree.** - After finding the Inorder successor make this node the next node of the root and root as the previous node of the Inorder successor.

- Return the
**leftmost node**of the tree as the head node of the doubly linked list which is formed from the given binary tree.

### Implementation

Below is the implementation of the approach which is discussed above for converting the given binary tree to the doubly linked list:

**C++ implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*// C++ program for converting the binary tree to a doubly linked list*
#include <bits/stdc++.h>
using namespace std;
*// Class of a node in the binary tree *
class Node {
public:
int val;
Node* left;
Node* right;
};
*// function which assigns the data to the newly formed node*
Node* newNode(int data) {
Node* new_Node = new Node();
new_Node->val = data;
new_Node->left = NULL;
new_Node->right = NULL;
return (new_Node);
}
*// main function which converts the given binary tree to the doubly linked list using recursion*
Node* bt_to_dll(Node* root) {
*// Base case when the root is NULL*
if (root == NULL)
return root;
*// Convert the left subtree and link to the root*
if (root->left != NULL) {
*// if the left subtree exists recursively call the function*
Node* left_t = bt_to_dll(root->left);
*// Find in order predecessor which is the right-most node in the subtree*
for (; left_t->right != NULL; left_t = left_t->right);
*// Make root as next of Inorder predecessor found*
left_t->right = root;
*// and also, make predecessor as previous of root node*
root->left = left_t;
}
*// Repeat the above steps for the right subtree if it exists*
if (root->right != NULL) {
*// recursively call the right subtree to convert it into a doubly linked list*
Node* right_t = bt_to_dll(root->right);
*// Find in order successor, which is the right of the root node*
for (; right_t->left != NULL; right_t = right_t->left);
*// Make root as the previous node of the Inorder successor*
right_t->left = root;
*// Make the Inorder successor next to the root node*
root->right = right_t;
}
*// return the root*
return root;
}
*// Main function which is used to convert the binary tree to DLL using the main recursive function*
Node* binaryTree_to_dll(Node* root) {
*// Base case if the root is NULL*
if (root == NULL)
return root;
*// Convert to DLL using bt_to_dll()*
root = bt_to_dll(root);
*// the leftmost root is the head of the doubly linked list*
while (root->left != NULL)
root = root->left;
*// return the head of the doubly linked list*
return (root);
}
*// Driver code*
int main() {
*// Let us create the tree shown in the above diagram*
Node* root = newNode(30);
root->left = newNode(40);
root->left->left = newNode(47);
root->left->right = newNode(19);
root->left->right->right = newNode(6);
root->right = newNode(15);
root->right->left = newNode(21);
root->right->right = newNode(18);
root->right->right->left = newNode(14);
*// Convert binary tree to DLL*
Node* head = binaryTree_to_dll(root);
*// Print the converted doubly linked list*
while (head != NULL) {
*// print the data present in every node of the doubly linked list*
cout << head->val << " ";
head = head->right;
}
return 0;
}

**Python implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*# python program to convert the binary tree to a doubly linked list*
*# class which represents each node in the newly formed doubly linked list*
class Node(object):
*# And also binary tree Node class has data, left and right child*
def __init__(self, item):
self.data = item
self.left = None
self.right = None
*# main function which converts given a binary tree to the doubly linked list using recursion*
def BT_to_DLL(root):
*# base case when the root is None*
if root is None:
return root
*# if left subtree exists recursively call the function*
if root.left:
*# finding the leftmost node in by calling recursively*
left_t = BT_to_DLL(root.left)
*# Find Inorder predecessor which is the right-most node in the subtree*
while left_t.right:
left_t = left_t.right
*# Make root as next of Inorder predecessor found*
left_t.right = root
*# and also, make predecessor as previous of root node*
root.left = left_t
*# Repeat the above steps for the right subtree if it exists*
if root.right:
*# recursively call the right subtree to convert it into doubly linked list*
right_t = BT_to_DLL(root.right)
*# Find in order successor, which is the right*
while right_t.left:
right_t = right_t.left
*# Make root as previous*
*# of successor*
right_t.left = root
*# Make successor as*
*# next of root*
root.right = right_t
return root
*# Driver function which is used to convert the binary tree to DLL using the main function *
def BinaryTree_to_DLL(root):
*# base case*
if root is None:
return root
*# Convert to the doubly linked list by using BT_to_DLL and calling it recursively*
root = BT_to_DLL(root)
*# to get the leftmost node in the tree because it is the head of the doubly linked list*
while root.left:
root = root.left
*# return the head of the doubly linked list which is formed from the given binary tree*
return root
*# Driver Code*
if __name__ == '__main__':
*# creatinf the binary tree by giving the values of nodes *
root = Node(30)
root.left = Node(40)
root.left.left = Node(47)
root.left.right = Node(19)
root.left.right.right = Node(6)
root.right = Node(15)
root.right.left = Node(21)
root.right.right = Node(18)
root.right.right.left = Node(14)
*# calling the function which converts the given binary tree to a doubly linked list*
head = BinaryTree_to_DLL(root)
*# printing the nodes in the doubly linked list*
while head:
*#printing the data in the node*
print(head.data, end = " ")
head = head.right

**Java implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*// Java program to convert the binary tree to a doubly linked list*
*// class which represents each node in the newly formed doubly linked list*
class Node {
int val;
Node left;
Node right;
*// constructor of the Node class*
Node(int data) {
val = data;
left = null;
right = null;
}
}
*// main class which consists of methods used for converting a binary tree to DLL *
class Solution {
Node root;
*// main function which converts a given binary tree to a doubly linked list using recursion*
Node bt_to_dll(Node root) {
*// Base case when the root is null*
if (root == null)
return root;
*// if left subtree exists recursively call the function*
if (root.left != null) {
*// finding the leftmost node by calling recursively*
Node left_t = bt_to_dll(root.left);
*// Find Inorder predecessor which is the rightmost node in the subtree*
for (; left_t.right != null; left_t = left_t.right);
*// Make root as next of Inorder predecessor found*
left_t.right = root;
*// and also, make predecessor as previous of root node*
root.left = left_t;
}
*// Repeat the above steps for right subtree if it exists*
if (root.right != null) {
*// recursively call the right subtree to convert it into a doubly linked list*
Node right_t = bt_to_dll(root.right);
*// Find Inorder successor, which is the right*
for (; right_t.left != null; right_t = right_t.left);
*// Make root as the previous node of the Inorder successor*
right_t.left = root;
*// Make the Inorder successor next to the root node*
root.right = right_t;
}
*// return the head of the doubly linked list*
return root;
}
*// Main function which is used to convert the binary tree to DLL using the main function *
Node binaryTree_to_dll(Node node) {
*// Base case when the root is null*
if (node == null)
return node;
*// Convert to DLL using bt_to_dll()*
node = bt_to_dll(node);
*// leftmost node is considered as the head of the doubly linked list*
while (node.left != null)
node = node.left;
*// return the head of the doubly linked list*
return node;
}
}
class Main{
*// Driver program*
public static void main(String[] args) {
*// creating the binary tree by inserting nodes*
Solution tree = new Solution();
*// creating a binary tree by inserting nodes *
tree.root = new Node(30);
tree.root.left = new Node(40);
tree.root.left.left = new Node(47);
tree.root.left.right = new Node(19);
tree.root.left.right.right = new Node(6);
tree.root.right = new Node(15);
tree.root.right.left = new Node(21);
tree.root.right.right= new Node(18);
tree.root.right.right.left = new Node(14);
*// Convert the given bt to dll*
Node head = tree.binaryTree_to_dll(tree.root);
*// Print the converted doubly linked list*
while (head != null) {
*// print the data present in every node of the doubly linked list*
System.out.print(head.val + " ");
head = head.right;
}
}
}

**Output:**

```
47 40 19 6 30 21 15 14 18
```

**Explanation:**

We can observe that the order of the doubly linked list is the same as the Inorder traversal on the given binary tree. The input binary tree is shown in the below.

The nodes of the binary tree are converted to the nodes of the doubly linked list. These nodes values are printed as the output. The doubly linked list formed is shown in the below image:

### Complexity Analysis

**Time Complexity:** *O*(*N*), where N is the number of nodes present in the given binary tree.

- Every node of the binary is traversed once to convert it into the doubly linked list.
- Therefore the overall time complexity of this approach is
*O*(*N*).

**Space Complexity:** *O*(*N*), where N is the number of nodes present in the given binary tree.

- Auxiliary stack space used during recursion.

## Approach 2: Fixing Left and Right Pointers

A solution for converting the binary tree to a doubly linked list is using the inorder traversal and manipulating the pointers of the root’s right and left pointer as the prev and next pointers as in the doubly linked list. This is can be achieved by simply performing the Inorder traversal on the given binary tree. And changing the left pointer using the previous pointer. Similarly, it changes the right pointer as the next pointer in the doubly linked list.

### Algorithm

The below algorithm clearly explains the above-discussed approach for converting the given binary tree to the doubly linked list:

- We simply do an Inorder traversal on a tree and keep track of previously visited nodes in the traversal.
- For fixing the previous pointers in the DLL, follow the below steps:
- While performing the Inorder traversal on the given binary tree, we keep track of the previously visited node and change the left pointer to the previous node.

- For fixing the next pointers in the DLL, follow the below steps:
- We use the left pointers of the node which are fixed as previous pointers of the DLL in the above step.
- We start traversing from the rightmost node in the given input binary tree. The rightmost node is however considered to be the last node in a formed doubly linked list. However, left pointers of the node are manipulated to point to the previous node in the doubly linked list.
- Now, we can linearly traverse the modified doubly linked list with the help of these previous pointers. The traversal goes from the rightmost node (last node) to the leftmost node (first node).
- While traversing the modified doubly linked list, we keep track of the previously visited node and modify the right pointer pointing to the previous node of the DLL.

### Implementation

Below is the implementation of the approach which is discussed above for converting the given binary tree to the doubly linked list: **C++ implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*// C++ program for converting the binary tree to a doubly linked list*
#include <bits/stdc++.h>
using namespace std;
*// Class of a node in the binary tree *
class Node {
public:
int val;
Node* left;
Node* right;
};
*// function which assigns the data to the newly formed node*
Node* newNode(int data) {
Node* new_Node = new Node();
new_Node->val = data;
new_Node->left = NULL;
new_Node->right = NULL;
return (new_Node);
}
*// Changes left pointers to as previous pointers in the newly converted dll *
void ChangePrevPtr(Node *root) {
static Node *pre = NULL;
if (root != NULL) {
*// converting it recursively *
*//keeping track of the previously visited node while doing an Inorder traversal on the binary tree*
ChangePrevPtr(root->left);
root->left = pre;
pre = root;
*// making them as the previous nodes in the dll *
ChangePrevPtr(root->right);
}
}
*// Changes right pointers to as next pointers in converted DLL*
Node *ChangeNextPtr(Node *node) {
*// assume the prev is initially None*
Node *previous = NULL;
*// For finding the rightmost node in Binary which is also the last node in the dll*
while (node && node->right != NULL)
node = node->right;
*// Start from the rightmost node, traverse back to the previous nodes using the left pointers which are manipulated in the above function*
*// While traversing change the right pointer of nodes as the next nodes in the dll*
while (node && node->left != NULL) {
previous = node;
node = node->left;
node->right = previous;
}
*// Return the head of the DLL, which is the leftmost node in the given binary tree*
return (node);
}
*// The main function that converts BST to DLL and returns the head of the converted DLL*
Node *BinaryTree_to_DLL(Node *root) {
*// Adjusts the previous pointers of the converted dll*
ChangePrevPtr(root);
*// Adjusts the next pointers of the converted DLL and returns the head of the dll *
return ChangeNextPtr(root);
}
*// Driver code*
int main() {
*// Let us create the tree shown in the above diagram*
Node* root = newNode(29);
root->left = newNode(-10);
root->left->left = newNode(56);
root->left->right = newNode(49);
root->left->right->left = newNode(8);
root->right = newNode(4);
root->right->right = newNode(1);
root->right->right->left = newNode(-14);
root->right->right->left->right = newNode(17);
*// Convert binary tree to DLL*
Node* head = BinaryTree_to_DLL(root);
*// Print the converted doubly linked list*
while (head != NULL) {
*// print the data present in every node of the doubly linked list*
cout << head->val << " ";
head = head->right;
}
return 0;
}

**Python implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*# Python program to convert the binary tree to dll*
*# node of a binary tree*
class Node:
*# Constructor to create a new tree node*
def __init__(self, val):
self.val = val
self.left = None
self.right = None
*# Changes left pointers to as previous pointers in the newly converted dll*
def ChangePrevPtr(root):
if root is not None:
*# converting it recursively *
*# keeping track of the previously visited node while doing an Inorder traversal on the binary tree*
ChangePrevPtr(root.left)
root.left = ChangePrevPtr.pre
ChangePrevPtr.pre = root
*# making them as the previous nodes in the dll *
ChangePrevPtr(root.right)
*# Changes right pointers to as next pointers in converted DLL*
def ChangeNextPtr(node):
*# assume the prev is initially None*
prev = None
*# For finding the rightmost node in Binary which is also the last node in the dll*
while(node and node.right != None):
node = node.right
*# Start from the rightmost node, and traverse back to the previous nodes using the left pointers which are manipulated in the above function*
*# While traversing change the right pointer of nodes as the next nodes in the DLL*
while(node and node.left != None):
prev = node
node = node.left
node.right = prev
*# Return the head of the DLL, which is the leftmost node in the given binary tree*
return node
*# The main function that converts BST to DLL and returns*
*# the head of DLL*
def BinaryTree_to_DLL(root):
*# Adjusts the previous pointers of the converted dll*
ChangePrevPtr(root)
*# Adjusts the next pointers of the converted DLL and returns the head of the dll *
return ChangeNextPtr(root)
*# driver code*
if __name__ == '__main__':
*# creatinf the binary tree by giving the values of nodes *
root = Node(29)
root.left = Node(-10)
root.left.left = Node(56)
root.left.right = Node(49)
root.left.right.left = Node(8)
root.right = Node(4)
root.right.right = Node(1)
root.right.right.left = Node(-14)
root.right.right.left.right = Node(17)
*# Static variable pre for function fixPrevPtr*
ChangePrevPtr.pre = None
*# calling the function which converts the given binary tree to a doubly linked list*
head = BinaryTree_to_DLL(root)
*# printing the nodes in the doubly linked list*
while head:
*#printing the data in the node*
print(head.val, end = " ")
head = head.right

**Java implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*// Java program to convert the binary tree to a doubly linked list*
public class Main{
*// class which represents each node in the newly formed doubly linked list*
static class Node {
int val;
Node left;
Node right;
*// constructor for creating the new node in the tree*
public Node(int val){
this.val = val;
}
}
*// assume the prev is initially None*
static Node prev;
*// Changes left pointers to as previous pointers in the newly converted dll*
static void ChangePrevptr(Node root) {
*// base case*
if (root == null)
return;
*// converting it recursively *
*//keeping track of the previously visited node while doing an Inorder traversal on the binary tree*
ChangePrevptr(root.left);
root.left = prev;
prev = root;
ChangePrevptr(root.right);
}
*// Changes right pointers to as next pointers in converted DLL*
static Node ChangeNextptr(Node node) {
*// For finding the rightmost node in Binary which is also the last node in the DLL*
while (node.right != null)
node = node.right;
*// Start from the rightmost node, traverse back to the previous nodes using the left pointers which are manipulated in the above function*
*// While traversing change right pointer of nodes as the next nodes in the DLL*
while (node != null && node.left != null) {
Node left_t = node.left;
left_t.right = node;
node = node.left;
}
*// Return the head of the DLL, which is the leftmost node in the given binary tree*
return node;
}
*// The main function that converts BST to DLL and returns the head of DLL*
static Node binaryTree_to_dll(Node root) {
prev = null;
*// Adjusts the previous pointers of the converted dll*
ChangePrevptr(root);
*// Adjusts the next pointers of the converted DLL and returns the head of the dll *
return ChangeNextptr(root);
}
*// Driver program*
public static void main(String[] args) {
*// creating a binary tree by inserting nodes *
Node root = new Node(29);
root.left = new Node(-10);
root.left.left = new Node(56);
root.left.right = new Node(49);
root.left.right.left = new Node(8);
root.right = new Node(4);
root.right.right = new Node(1);
root.right.right.left = new Node(-14);
root.right.right.left.right = new Node(17);
*// Convert the given bt to dll*
Node head = binaryTree_to_dll(root);
*// Print the converted doubly linked list*
while (head != null) {
*// print the data present in every node of the doubly linked list*
System.out.print(head.val + " ");
head = head.right;
}
}
}

**Output:**

```
56 -10 8 49 29 4 -14 17 1
```

**Explanation:**

We can observe that the order of the doubly linked list is the same as the Inorder traversal on the given binary tree. The input binary tree is shown in the below image.

The nodes of the binary tree are converted to the nodes of the doubly linked list. These nodes’ values are printed as the output. The doubly linked list formed is shown in the below image:

### Complexity Analysis:

**Time Complexity:** *O*(*N*), where N is the number of nodes present in the given binary tree.

- Every node of the binary is traversed twice to convert it into the doubly linked list. Because two traversals are performed on the tree.
- One traversal is performed to change the left pointers as the previous pointers and the other traversal for changing the right pointers as the next pointers in the doubly linked list.
- Therefore the overall time complexity of this approach is
*O*(*N*).

**Space Complexity:** *O*(*N*), where N is the number of nodes present in the given binary tree.

- An auxiliary stack space of
*O*(*N*) is used during recursion to keep track of the visited nodes during the Inorder traversal which is performed on the given tree.

## Approach 3: Inorder Traversal (By Keeping Track Of DLL Head and Tail Pointers)

All the approaches discussed earlier deals with Inorder traversal and manipulating the left and right pointers of a node as the prev and next pointers to convert it into a doubly linked list. Similarly, this approach uses recursion to recursively convert the left subtree and right subtree separately and convert them into a doubly linked list. While traversing each node keep track of the head node and tail node of the DLL.

### Algorithm

The below algorithm converts the given binary tree into a doubly linked list using recursion:

- Firstly, traverse the whole binary tree in an Inorder manner (left node of the root is processed first, the present node is inserted into the DLL with the help of the tail pointer, then the right node is processed).
- For every node which is visited, keep track of the head and tail pointers that are initialized for a doubly linked list.
- Insert every visited node to the end of the doubly linked list with the help of the tail pointer. By adding it to the tail pointer.
- Head pointer always has the first node of the doubly linked list.
- Return the head pointer at the end of all recursive calls i.e, when all the nodes in the tree are visited.

### Implementation

Below is the implementation of the approach which is discussed above for converting the given binary tree to the doubly linked list.

**C++ implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*// C++ program for converting the binary tree to a doubly linked list*
#include <bits/stdc++.h>
using namespace std;
*// Class of a node in the binary tree *
class Node {
public:
int val;
Node* left;
Node* right;
};
*// function which assigns the data to the newly formed node*
Node* newNode(int data) {
Node* new_Node = new Node();
new_Node->val = data;
new_Node->left = NULL;
new_Node->right = NULL;
return (new_Node);
}
*// recursive function which helps in converting the Binary tree to dll *
*// head is the head of the formed dll*
*// tail is the ending node of the formed dll*
*// initially they are null*
void bt_to_dll(Node* root, Node** head, Node** tail) {
*// base case if the root is NULL*
if (root == NULL)
return;
*// recursively call for the left subtree of the root*
bt_to_dll(root->left, head, tail);
*// if the head is null that means the root is the first node in the dll*
if (*head == NULL) {
*head = root;
}
*// make tail as the root to the left node*
root->left = *tail;
*// finding the last rightmost node which is the tail of the dll*
if (*tail != NULL)
*// finding the tail of the dll*
(*tail)->right = root;
*// assign root as the tail node*
*tail = root;
*// recursively call for the right subtree of the root*
bt_to_dll(root->right, head, tail);
}
*// The main function which helps in calling the recursive function which is mentioned above*
Node* BinaryTree_to_DLL(Node* root) {
*// Base case*
if (root == NULL)
return root;
*//initializing the head and tail pointer as NULL*
Node* head = NULL;
*//initializing the tail pointer of the dll*
Node* tail = NULL;
*// passing root, head, and tail for the recursive function to convert the given binary tree to dll*
bt_to_dll(root, &head, &tail);
*// return the head of the converted dll*
return head;
}
*// Driver code*
int main() {
*// Let us create the tree shown in the above diagram*
Node* root = newNode(10);
root->left = newNode(8);
root->left->left = newNode(14);
root->left->right = newNode(94);
root->right = newNode(16);
root->left->left->left = newNode(27);
root->left->left->left->right = newNode(29);
*// Convert binary tree to DLL*
Node* head = BinaryTree_to_DLL(root);
*// Print the converted doubly linked list*
while (head != NULL) {
*// print the data present in every node of the doubly linked list*
cout << head->val << " ";
head = head->right;
}
return 0;
}

**Python implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*# Python program to convert the binary tree to dll*
*# node of a binary tree*
class Node:
*# Constructor to create a new tree node*
def __init__(self, val):
self.val = val
self.left = None
self.right = None
*# intialising the global variables which are the head and tail of the DLL*
head,tail=None,None
*# Recusive function which helps in converting the binary tree to the doubly linked list*
def bt_to_dll(root):
*# base case *
if (root == None):
return
*# getting the left and right pointers of the DLL*
left = root.left
right = root.right
*# global variables which are the head and tail of the DLL*
global head
global tail
*# recursive calls for the left subtree of the root*
bt_to_dll(root.left)
*# base case*
if (head == None):
head = root
root.left = tail
*#rightmost node is the tail of the converted DLL*
if (tail != None):
tail.right = root
tail = root
*# recursively call for the right side of the root(right subtree)*
bt_to_dll(root.right)
*# main function which calls the recursive function and helps in converting the binary tree to dll*
def BinaryTree_to_DLL(root):
*# Base case*
global head
if (root == None):
head = root
*# calling the recursive function *
bt_to_dll(root)
*# driver code*
if __name__ == '__main__':
*# creatinf the binary tree by giving the values of nodes *
root = Node(10)
root.left = Node(8)
root.left.left = Node(14)
root.left.right = Node(94)
root.left.left.left = Node(27)
root.left.left.left.right = Node(29)
root.right = Node(16)
*# calling the function which converts the given binary tree to a doubly linked list*
BinaryTree_to_DLL(root)
*# printing the nodes in the doubly linked list*
while head:
*#printing the data in the node*
print(head.val, end = " ")
head = head.right

**Java implementation** for converting the given binary tree to the doubly linked list by processing subtrees:

*// Java program to convert the binary tree to a doubly linked list*
public class Main{
*// class which represents each node in the newly formed doubly linked list*
static class Node {
int val;
Node left;
Node right;
*// constructor for creating the new node in the tree*
public Node(int val){
this.val = val;
}
}
*//initializing the global variables which are the head and tail of the DLL*
static Node head, tail;
*// Recursive function which helps in converting the binary tree to the doubly linked list*
static void bt_to_dll(Node root) {
*// base case if the root is null *
if (root == null)
return;
*// getting the left and right pointers of the dll*
Node left = root.left;
Node right = root.right;
*// recursive calls for the left subtree of the root*
bt_to_dll(root.left);
*// base case if the head is null, it means it is the starting point of the dll*
if (head == null)
head = root;
root.left = tail;
*// rightmost node is the tail of the converted DLL*
if (tail != null)
(tail).right = root;
tail = root;
*// recursively call for the right side of the root(right subtree)*
bt_to_dll(root.right);
}
*// main function which calls the recursive function and helps in converting the binary tree to dll*
static void binaryTree_to_dll(Node root) {
*// Base case*
if (root == null)
head = root;
*// calling the recrusive function *
bt_to_dll(root);
}
*// Driver program*
public static void main(String[] args) {
*// creating a binary tree by inserting nodes *
Node root = new Node(10);
root.left = new Node(8);
root.left.left = new Node(14);
root.left.right = new Node(94);
root.left.left.left = new Node(27);
root.left.left.left.right = new Node(29);
root.right = new Node(16);
*// Convert the given bt to dll*
binaryTree_to_dll(root);
*// Print the converted doubly linked list*
while (head != null) {
*// print the data present in every node of the doubly linked list*
System.out.print(head.val + " ");
head = head.right;
}
}
}

**Output:**

```
27 29 14 8 94 10 16
```

**Explanation:** We can observe that the order of the doubly linked list is the same as the Inorder traversal on the given binary tree. The input binary tree is shown in the below image.

The nodes of the binary tree are converted to the nodes of the doubly linked list. These nodes’ values are printed as the output. The doubly linked list formed is shown in the below image:

### Complexity Analysis

**Time Complexity:** *O*(*N*), where N is the number of nodes present in the given binary tree.

- Every node of the binary is traversed once during the Inorder traversal and converted into head and tail pointers as in the doubly linked list.
- Therefore the overall time complexity of this approach is
*O*(*N*).

**Space Complexity:** *O*(*N*), where N is the number of nodes present in the given binary tree.

- Auxiliary stack space used during recursion for Inorder traversal performed on the given input binary tree.

## Conclusion

- This article explained different approaches used to convert a given binary tree into a doubly linked list.
- All the approaches dealt with manipulating the left and right pointers of the tree into prev and next pointers as in the doubly linked list.
- Every approach uses Inorder traversal while converting into a doubly linked list.
- Time complexity of all the approaches is
*O*(*N*), and space complexity is*O*(*N*). The difference between all the approaches is how the pointers are changed to make it a doubly linked list. - Please refer to Part 2 of this editorial for recursive and iterative approach.