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

In Part 1 of this editorial we discussed three approaches, namely –

- Approach 1: By Processing Subtrees
- Approach 2: Fixing Left and Right Pointers
- Approach 3: Inorder Traversal (By Keeping Track Of DLL Head and Tail Pointers)

In this part we will discuss about recursive and iterative approaches.

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

## Approach 4: Using Recursion

This approach uses recursion to convert the given input binary tree into a doubly linked list. This solution is considered to be the simplest of the above approaches. This approach also uses Inorder traversal for manipulating the pointers of the binary tree to convert to a doubly linked list. In this approach, while performing an Inorder traversal on the given binary tree we need to keep track of previously visited nodes. In this approach we are just manipulating the right and left pointers to next and prev pointers of DLL unlike the above approach using tail pointer. We follow the Inorder traversal manner so that we can change the left and right pointers as the prev and next pointers to convert them into the doubly linked list.

### Algorithm

Below algorithm clearly explains the above approach:

- Start traversing the given binary tree in an Inorder fashion, for every visited node follow the below steps:
- Keep track of the previously visited node in a variable, assume previous.
- And for every visited node, make its next pointing to the previous and previous of this node as the prev.

- In this Inorder fashion given input binary tree is converted into a doubly linked list.

### 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);
}
*// A recursive function which converts the given binary tree to the doubly linked list*
*// head is the first node in the formed dll*
*// root is the root of the given binary tree*
void BinaryTree_to_DLL(Node* root, Node** head) {
*// Base case if the root is null*
if (root == NULL)
return;
*// Initialize previously visited "prev" node as NULL*
static Node* prev = NULL;
*// Recursively convert the left subtree of the root node*
BinaryTree_to_DLL(root->left, head);
*// if prev is null, that means the root is the head node of the dll *
if (prev == NULL)
*head = root;
*// else find the end of the DLL by traversing the right side*
else {
root->left = prev;
prev->right = root;
}
*// make the prev as the root node*
prev = root;
*// recursively call the right subtree of the root node*
BinaryTree_to_DLL(root->right, head);
}
*// Driver code*
int main() {
*// creating the tree by inserting nodes and corresponding node values into it *
Node* root = newNode(15);
root->left = newNode(-45);
root->left->left = newNode(-10);
root->left->left->left = newNode(-20);
root->left->left->left->left = newNode(-40);
root->right = newNode(10);
root->right->right = newNode(40);
root->right->right->right = newNode(20);
root->right->right->right->right = newNode(45);
*// Convert binary tree to DLL by calling the function*
Node* head = NULL;
BinaryTree_to_DLL(root, &head);
*// 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
*# global variable used in the below recursive function*
prev = None
*# Main function which is used to convert the given binary tree to the DLL using recursion*
def BinaryTree_to_DLL(root):
*# Base case if the root is None*
if root is None:
return root
*# Recursively call the function for the left subtree of the subtree*
head = BinaryTree_to_DLL(root.left);
*# we need to use the global keyword for prev because we are going to change prev*
global prev
*# If prev is empty, then this is the first node of DLL*
if prev is None :
*# make the head of the dll*
head = root
*# else get the next node of the prev node*
else:
root.left = prev
prev.right = root
*# Update the value of the prev*
prev = root;
*# Recursively call the function for the right subtree of the subtree*
BinaryTree_to_DLL(root.right);
*# return the head of the converted DLL*
return head
*# driver code*
if __name__ == '__main__':
*# creatinf the binary tree by giving the values of nodes *
root = Node(15)
root.left = Node(-45)
root.left.left = Node(-10)
root.left.left.left = Node(-20)
root.left.left.left.left = Node(-40)
root.right = Node(10)
root.right.right = Node(40)
root.right.right.right = Node(20)
root.right.right.right.right = Node(45)
*# 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*
*// A binary tree node has data, left pointers, and right pointers*
class Node {
int val;
Node left;
Node right;
*// constructor for creating the new node in the tree*
public Node(int val) {
this.val = val;
left = right = null;
}
}
class Solution {
*// root the given binary tree*
Node root;
*// head is the first node in the formed dll*
Node head;
*// Initialize previously visited node as NULL*
static Node prev = null;
*// Print the converted doubly linked list*
void print_DLL(Node head) {
while (head != null) {
*// print the data present in every node of the doubly linked list*
System.out.print(head.val + " ");
head = head.right;
}
}
*// A recursive function which converts the given binary tree to the doubly linked list*
*// root is the root of the given binary tree*
void binaryTree_to_dll(Node root) {
*// Base case if the root is null*
if (root == null)
return;
*// Recursively convert the left subtree of the root node*
binaryTree_to_dll(root.left);
*// if prev is null, that means the root is the head node of the dll *
if (prev == null){
head = root;
}
*// else find the end of the DLL by traversing the right side*
else {
root.left = prev;
prev.right = root;
}
*// make the prev as the root node*
prev = root;
*// recursively call the right subtree of the root node*
binaryTree_to_dll(root.right);
}
*// Driver program to test above functions*
public static void main(String[] args) {
*// Let us create the tree as shown in the above diagram*
Solution tree = new Solution();
tree.root = new Node(15);
tree.root.left = new Node(-45);
tree.root.right = new Node(10);
tree.root.left.left = new Node(-10);
tree.root.left.left.left = new Node(-20);
tree.root.left.left.left.left = new Node(-40);
tree.root.right.right = new Node(40);
tree.root.right.right.right = new Node(20);
tree.root.right.right.right.right = new Node(45);
*// function called which converts binary tree to DLL*
tree.binaryTree_to_dll(tree.root);
*// Print the converted DLL*
tree.print_DLL(tree.head);
}
}

**Output:**

```
-40 -20 -10 -45 15 10 40 20 45
```

**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, therefore to convert the binary tree into a doubly linked list 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 5: Iterative Approach

All the above approaches deal with recursion, using an Inorder traversal we convert the binary tree to a doubly linked list. Inorder traversal can also be performed iteratively. Iterative Inorder traversal requires a stack data structure for keeping track of the visited nodes and their current level. Every node is inserted into the stack and a depth first traversal is performed to obtain the deepest leaf node first, then the right node, so in this way the tree is traversed in an Inorder fashion. Here the value of the level indicates whether the node’s left is processed or node is processed or node’s right is processed or not.

### Algorithm

The below algorithm clearly explains the iterative Inorder traversal performed on the tree to convert it into a doubly linked list:

- Traversal is performed using the stack data structure of pair type. Firstly initialize the stack of type pair, because it has to store
`<Node, int>`

and insert a pair(root node,`0`

). Using a while loop on the stack, until the stack is empty, perform the below steps:- Pop the top element from the stack and extract its node and level separately.
- If the level is
`3`

or the node’s value is Null, this is the base and we can move to the next top element in the stack. - If that’s not the case then push the [root, level+1] into the stack.
- Now, we need to check whether the extracted level has the value of
`0`

, it indicates that we need to process the left side of the node. If the level is`0`

whenever just push the node’s left and level=0 [node.left, 0] into the stack. - If the level is
`1`

, then we need to process the node in it by converting it into a node of the doubly linked list. Check whether the prev is None, if the prev pointer is null and the flag is true, it indicates the present node is the first node in the doubly linked list and makes this the head of the doubly linked list. Change the value of the flag indicating the head of a doubly linked list is already discovered. - If the level is
`2`

, it indicates that the present node’s left is processed, the node’s data is also processed and we need to process the right tree of the node, so we need to push [node.right, 0] into the stack.

- Whenever the level is
`0`

, it means it that the node is processed for the first time. Where as level`1`

indicates it’s the second time it is traversed, so we try to process it.

### 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);
}
*// iterative in order traversal on the given binary tree to convert it into dll*
*// root is the root of the given binary tree*
Node *BinaryTree_to_DLL(Node *root) {
*// stack is used for an iterative approach to keep track of nodes*
stack<pair<Node*, int>> st;
*// first push the root node with the level as 0*
st.push({root, 0});
*// flag here indicates whether we got the head of the doubly linked list or not*
bool flag = true;
*// head of the dll*
Node* head = NULL;
*//initialize the prev as NULL initially*
Node* prev = NULL;
*// traverse the tree while the stack is not empty*
while(!st.empty()) {
*// get the top element of the stack*
auto n = st.top();
*// get the node *
Node* node = n.first;
*// get the level of the top node*
int level = n.second;
*// pop the top element of the stack*
st.pop();
*// check whether the level is 3 and the node is null *
if(level == 3 or node == NULL)
continue;
*// else push the node in the stack and increment the level by 1*
st.push({node, level+1});
*// if the level is 0, then push the node's left to the stack*
if(level == 0)
st.push({node->left, 0});
*// if the level is 1*
else if(level == 1) {
*// check whether the prev is null*
*// if null is not null then it is not the first node of the dll*
if(prev)
*// make prev's next node as the node*
prev->right = node;
*// if null then it is the first node of the dll*
node->left = prev;
prev = node;
*//converting the given node to the node of the dll*
if(flag) {
*// make the node the head *
head = node;
*// flag is false because we got the head of the DLL, we don't need to update again*
flag = false;
}
}
*// check if the level is 2*
*// if the level is 2, push the right subtree into the stack*
else if(level == 2) {
st.push({node->right, 0});
}
}
return head;
}
*// Driver code*
int main() {
*// Let us create the tree shown in the above diagram*
Node* root = newNode(20);
root->left = newNode(18);
root->left->left = newNode(17);
root->left->left->right = newNode(19);
root->left->left->right->left = newNode(22);
root->right = newNode(24);
root->right->left = newNode(-10);
root->right->left->right = newNode(40);
root->right->left->right->left = newNode(57);
*// Convert binary tree to DLL*
Node* head = NULL;
head= BinaryTree_to_DLL(root);
*//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
*# iterative in order traversal on the given binary tree to convert it into dll*
*# root is the root of the given binary tree*
def BinaryTree_to_DLL(root):
*# using a stack *
st = []
*# push the root node with the level as 0*
st.append([root, 0])
*# flag is used to keep track of the head of the DLL *
flag = True
*# the head of the DLL*
head = None
*# prev used in DLL*
prev = None
*# traverse the tree until the stack is empty*
while len(st) > 0:
*# pop the top element in the stack*
s = st.pop()
*# extract the node from the popped element*
node = s[0]
*# extract the value of the level of that particular node*
level = s[1]
*# check whether the level of the node is 3*
*# base case*
if level == 3 or node == None:
continue
*# else push the node with the incrementing the level by 1*
st.append([node, level+1])
*# if the level is 0, then push the node's left tree into the stack*
if level == 0:
st.append([node.left, 0])
*# if the level is 1, process the present node and convert its pointers to make it a dll*
elif level == 1:
*# if prev is None then it is not the first node of the dll*
if prev != None:
prev.right = node
*# make the node's left as the prev*
node.left = prev
*# update the value of prev*
prev = node
*# if the flag is true, then the node is the first node in the DLL*
if flag:
*# make the head of the DLL*
head = node
flag = False
*# if the level is 2, then push the right subtree of the root with the level0*
elif level == 2:
st.append([node.right, 0])
return head
*# driver code*
if __name__ == '__main__':
*# creatinf the binary tree by giving the values of nodes *
root = Node(20);
root.left = Node(18);
root.left.left = Node(17);
root.left.left.right = Node(19);
root.left.left.right.left = Node(22);
root.right = Node(24);
root.right.left = Node(-10);
root.right.left.right = Node(40);
root.right.left.right.left = Node(57);
*# 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*
import java.util.*;
import javafx.util.Pair;
public class Solution{
*// 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;
}
}
*// iterative in order traversal on the given binary tree to convert it into dll*
*// root is the root of the given binary tree*
static Node binaryTree_to_dll(Node root) {
*// stack is used for an iterative approach to keep track of nodes*
Stack<Pair<Node,Integer>> st = new Stack<Pair<Node,Integer>>();
*// first push the root node with the level as 0*
st.push(new Pair<Node,Integer>(root, 0));
*// flag here indicates whether we got the head of the doubly linked list or not*
boolean flag = true;
*// head of the dll*
Node head = null;
*//initialize the prev as NULL initially*
Node prev = null;
*// traverse the tree while the stack is not empty*
while (!st.empty()) {
*// get the top element of the stack*
Pair<Node,Integer> t = st.peek();
*// get the node *
Node node = t.getKey();
*// get the level of the top node*
int level = t.getValue();
*// pop the topmost node *
st.pop();
*// check whether the level is 3 and the node is null *
if (level == 3 || node == null)
continue;
*// else push the node in the stack and increment the level by 1*
st.push(new Pair<Node,Integer>(node, level + 1));
*// if the level is 0, then push the node's left to the stack*
if (level == 0)
st.push(new Pair<Node,Integer>(node.left, 0));
*// if the level is 1*
else if (level == 1) {
*// check whether the prev is null*
*// if null is not null then it is not the first node of the dll*
if (prev != null)
prev.right = node;
*// if null then it is the first node of the dll*
node.left = prev;
prev = node;
*// converting the given node to the node of the dll*
if (flag) {
*// make the node the head *
head = node;
*// flag is false because we got the head of the DLL, we don't need to update again*
flag = false;
}
}
*// check if the level is 2*
*// if level is 2, push the right subtree into the stack*
else if (level == 2)
st.push(new Pair<Node,Integer>(node.right, 0));
}
return head;
}
*// Driver program*
public static void main(String[] args) {
*// creating a binary tree by inserting nodes *
Node root = new Node(20);
root.left = new Node(18);
root.left.left = new Node(17);
root.left.left.right = new Node(19);
root.left.left.right.left = new Node(22);
root.right = new Node(24);
root.right.left = new Node(-10);
root.right.left.right = new Node(40);
root.right.left.right.left = new Node(57);
*// 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:**

`17 22 19 18 20 -10 57 40 24 `

**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 once to convert it into the doubly linked list, if the level of the node in the stack is
`0`

, it is again pushed into the stack by incrementing the level, so every node is traversed twice. - Therefore the overall time complexity of this approach is $O(N+ N)$.

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

- Extra space is needed during the iterative Inorder traversal on the given binary tree which uses stack data structure for keeping track of the nodes.
- The maximum number of elements in a stack is N, therefore the space complexity is $O(N)$.

## 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.
- Out of all these approaches Approach
`4`

is considered to be simple and more efficient. - Approach
`5`

uses the iterative Inorder traversal unlike other approaches to convert the binary tree into a doubly linked list.