# Convert a Binary Tree to Doubly Linked List

Posted in  Vinay Khatri
Last updated on November 30, 2023

You are given a Binary Tree. Your task is to convert it into a doubly-linked list. The left and right child of the nodes of the Binary Tree is to be converted into previous and next pointers of the linked list, respectively. Nodes of the doubly linked list must be according to the inorder of the binary tree. The leftmost node or the first node of the inorder of the tree will be the head of the tree.

### Approach 1

In this approach, we will traverse the tree twice: first for fixing the left pointer and again for fixing the right pointer.

Fixing the left pointer: This is the first step of this approach. We will iterate through the tree in an inorder fashion and will keep track of the previously visited node so that we can change the left pointer to the previous node.

Fixing the right pointer: This is complex as compared to the previous step. We will be using the left pointers fixed in step one. Since the right-most node is the last node of the doubly linked list, we will start from there. We will traverse the tree linearly as the left pointers are already pointing to the previous nodes. We will keep track of the previously visited node and change the right pointer to the previous node during traversal.

### Algorithm

1. Create a node with the value being set as the data that is passed as the parameter and initialize its left and right children to NULL.
2. Traverse the binary tree in inorder traversal while updating the previous pointers in the list, with the left child nodes.
3. Traverse the binary tree in inorder traversal while updating the next pointers in the list with the right child nodes.
4. Traverse the tree and get the DLL's last node, or the node at the farthest right side of the tree
5. Now, for updating the right pointers by traversing backward from the farthest right node with the help of the left nodes.
6. Traverse over the doubly linked list from the left node to the right node to print it.

The implementation of the above-discussed approach is:

### CPP

```#include <bits/stdc++.h>
using namespace std;

// Class for a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
class node
{
public:
int data;
node *left, *right;
};

// function to create a node
// with the value being set as the data
// that is passed as the parameter,
// and initializing its left and right children to NULL
node *newNode(int data)
{
node *Node = new node();
Node->data = data;
Node->left = Node->right = NULL;
return(Node);
}

// function to traverse tree in an
// inorder fashion
void inorder(node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << " " << root->data;
inorder(root->right);
}
}

// function to traverse the binary tree
// in inorder traversal, while
// updating the previous pointers
// in the list, with the left child nodes.
void setPrevPtr(node *root)
{
static node *pre = NULL;

if (root != NULL)
{
setPrevPtr(root->left);
root->left = pre;
pre = root;
setPrevPtr(root->right);
}
}

// function to traverse the binary tree
// in inorder traversal, while
// updating the next pointers
// in the list, with the right child nodes.
node *setNextPtr(node *root)
{
node *prev = NULL;

// to traverse the tree and
// get the DLL's last node, or
// the node at farthest right side
// in the tree
while (root && root->right != NULL)
root = root->right;

// now, for updating the right pointers
// by traversing backwards,
// from the farthest right node
// with the help of the left nodes.
while (root && root->left != NULL)
{
prev = root;
root = root->left;
root->right = prev;
}

// i.e., the node at the farthest left side.
return (root);
}

// function to transform the binary tree
node *convertBT(node *root)
{
// for the setting of the previous pointer
setPrevPtr(root);

// for the setting of the next pointer
return setNextPtr(root);
}

// to print, traverse over the doubly linked list
// from the left node to the right node.
void printDLL(node *root)
{
while (root != NULL)
{
cout<<" "<data;
root = root->right;
}
}

// Driver code
int main(void)
{
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);

cout<<"Inorder Tree:\n";
inorder(root);

cout << "\nConverted Doubly Linked List:\n";
return 0;
}

```

### Output

```Inorder Tree:
25 12 30 10 36 15
25 12 30 10 36 15``` ### JAVA

```public class ConvertBT
{
static class node
{
int data;
node left, right;

public node(int data)
{
this.data = data;
}
}

static node prev;

// function to traverse the binary tree
// in inorder traversal, while
// updating the previous pointers
// in the list, with the left child nodes.
static void setPrevPtr(node root)
{
if (root == null)
return;

setPrevPtr(root.left);
root.left = prev;
prev = root;
setPrevPtr(root.right);

}

// function to traverse the binary tree
// in inorder traversal, while
// updating the next pointers
// in the list, with the right child nodes.
static node setNextPtr(node root)
{
// to traverse the tree and
// get the DLL's last node, or
// the node at farthest right side
// in the tree
while (root.right != null)
root = root.right;

// now, to updating the right pointers
// by traversing backwards,
// from the farthest right node
// with the help of the left nodes.
while (root != null && root.left != null)
{
node left = root.left;
left.right = root;
root = root.left;
}

// i.e., the node at the farthest left side.
return root;
}

// method to transform the binary tree
static node BTTtoDLL(node root)
{
prev = null;

// for the setting of the previous pointer
setPrevPtr(root);

// for the setting of the next pointer
return setNextPtr(root);
}

// to print, traverse over the doubly linked list
// from the left node to the right node.
static void printDLL(node root)
{
while (root != null)
{
System.out.print(" ");
System.out.print(root.data + " ");
root = root.right;
}
}

// function to traverse tree in an
// inorder fashion
static void inorder(node root)
{
if (root == null)
return;
inorder(root.left);
System.out.print(" ");
System.out.print(root.data + " ");
inorder(root.right);
}

public static void main(String[] args)
{
node root = new node(10);
root.left = new node(12);
root.right = new node(15);
root.left.left = new node(25);
root.left.right = new node(30);
root.right.left = new node(36);

System.out.println("Inorder Tree:");
inorder(root);

}
}
```

### Output

```Inorder Tree:
25 12 30 10 36 15
25 12 30 10 36 15``` ### Python

```# Class for a node
# having an integer value, data
# and two pointers
# to store the references of the
# left and right children
class Node:

# constructor to create a node
# with the value being set as the data
# that is passed as the parameter,
# and initializing its left and right children to NULL
def __init__(self, data):
self.data = data
self.left = None
self.right = None

# function to traverse tree in an
# inorder fashion
def inorder(root):

if root is not None:
inorder(root.left)
print (" %d" %(root.data))
inorder(root.right)

# function to traverse the binary tree
# in inorder traversal, while
# updating the previous pointers
# in the list, with the left child nodes.
def setPrevPtr(root):
if root is not None:
setPrevPtr(root.left)
root.left = setPrevPtr.pre
setPrevPtr.pre = root
setPrevPtr(root.right)

# function to traverse the binary tree
# in inorder traversal, while
# updating the next pointers
# in the list, with the right child nodes.
def setnextPtr(root):

prev = None
# to traverse the tree and
# get the DLL's last node, or
# the node at farthest right side
# in the tree
while(root and root.right != None):
root = root.right

# now, to updating the right pointers
# by traversing backwards,
# from the farthest right node
# with the help of the left nodes.
while(root and root.left != None):
prev = root
root = root.left
root.right = prev

# i.e., the node at the farthest left side.
return root

# function to transform the binary tree
# into a doubly linked list.
def ConvertBT(root):

# for the setting of the previous pointer
setPrevPtr(root)

# for the setting of the next pointer
return setnextPtr(root)

# to print, traverse over the doubly linked list
# from the left node to the right node.
def printDLL(root):
while(root != None):
print (" %d" %(root.data))
root = root.right

# Driver program to test above function
root = Node(10)
root.left = Node(12)
root.right = Node(15)
root.left.left = Node(25)
root.left.right = Node(30)
root.right.left = Node(36)

print ("Inorder Tree:")
inorder(root)

setPrevPtr.pre = None

```

### Output

```Inorder Tree:
25 12 30 10 36 15
25 12 30 10 36 15``` Time Complexity: O(n), where n is the number of nodes. Because we are simply traversing the tree twice in the inorder fashion.

### Approach 2

This approach is simpler than the previous one. In this approach, we will iterate over the tree in the inorder fashion and keep a track of the node that has been traversed, let’s say prev. Now, for every visited node, update it as the next of prev and previous of this node as prev .

### Algorithm

1. Recursively convert the binary tree whose root has been passed to it as a parameter to a doubly linked list, whose head has also been passed to it as a parameter.
2. Convert recursively the right subtree into dll.
3. Place the root of the binary tree into the doubly linked list.
4. Update the previous head using the left pointer
6. Print, traverse over the doubly linked list.
7. Convert recursively the right subtree into dll.
8. From the left node to the right node.
9. Traverse from left node to right node to print.

The implementation of the above-discussed approach is:

### CPP

````#include <bits/stdc++.h>
using namespace std;
// Structure for a node and tree
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
struct Node {
int data;
Node *left, *right;
};

// function to create a node
// with the value being set as the data
// that is passed as the parameter,
// and initializing its left and right children to NULL
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}

// function to recursively convert the binary tree
// whose root has been passed to it as a parameter
// to it as a parameter.
{
// Base cases
if (root == NULL)
return;

// convert recursively the right subtree
// into dll.

// placing the root of the
// binary tree into the

// using the left pointer

// convert recursively the left subtree
// into dll.
}

// to print, traverse over the doubly linked list
// from the left node to the right node.
{
cout << "Converted Doubly Linked List:\n";
cout << " " << head->data;
}
}

int main()
{

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

return 0;
}
```

### Output

```Converted Doubly Linked List:
25 12 30 10 36 15``` ### JAVA

```// class for a node and tree
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
class Node {
int data;
Node left, right;

public Node(int data)
{
this.data = data;
left = right = null;
}
}

class BinaryTree {
Node root;

// function to recursively convert the binary tree
// whose root has been passed to it as a parameter
// to a doubly linked list, whose head as also been passed
// to it as a parameter.
void ConverBT(Node root)
{
// Base cases
if (root == null)
return;

// convert recursively the right subtree
// into dll
ConverBT(root.right);

// placing the root of the
// binary tree into the

// using the left pointer

// convert recursively the left subtree
// into dll.
ConverBT(root.left);
}

// to print, traverse over the doubly lined list
// from the left node to the right node.
{
}
}

public static void main(String[] args)
{

BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(12);
tree.root.right = new Node(15);
tree.root.left.left = new Node(25);
tree.root.left.right = new Node(30);
tree.root.right.left = new Node(36);

tree.ConverBT(tree.root);
}
}
```

### Output

```Converted Doubly Linked List:
25 12 30 10 36 15``` ### Python

```# class for a node and tree
# having an integer value, data
# and two pointers
# to store the references of the
# left and right children
class Node:
def __init__(self, data):
self.data = data
self.left = self.right = None

class BinaryTree:
# function to recursively convert the binary tree
# whose root has been passed to it as a parameter
# to a doubly linked list, whose head as also been passed
# to it as a parameter.

def ConvertBT(self, root: Node):
if root is None:
return

# convert recursively the right subtree
# into dll
self.ConvertBT(root.right)

# placing the root of the
# binary tree into the

# using the left pointer

# convert recursively the left subtree
# into dll
self.ConvertBT(root.left)

if __name__ == '__main__':

tree = BinaryTree()
tree.root = Node(10)
tree.root.left = Node(12)
tree.root.right = Node(15)
tree.root.left.left = Node(25)
tree.root.left.right = Node(30)
tree.root.right.left = Node(36)

tree.ConvertBT(tree.root)
```

### Output

```Converted Doubly Linked List:
25 12 30 10 36 15``` Time Complexity: O(n), where n is the number of nodes. Because we are simply applying the inorder traversal.

### Approach 3

The basic idea of this approach is that we perform the inorder traversal over the tree. Add nodes at the starting of the current linked list and update the head of the list. Because we are adding the node at the start, we have to operate leaf nodes in the reverse order.

### Algorithm

1. Create a static variable to store the node visited previously.
2. Convert recursively the left subtree into dll.
3. Convert recursively the right subtree into dll.
4. Traverse over the doubly linked lis from the left node to the right node to print.

The implementation of the above-discussed approach is

### CPP

```#include
using namespace std;

// Structure for a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
struct node
{
int data;
node* left;
node* right;
};

// function to recursively convert the binary tree
// whose root has been passed to it as a parameter
// to it as a parameter.
{
// Base case
if (root == NULL) return;

// static variable to
// store the node visited previously.
// initialize it to null
static node* prev = NULL;

// convert recursively the left subtree
// into dll.

if (prev == NULL)
else
{
root->left = prev;
prev->right = root;
}
prev = root;

// convert recursively the right subtree
// into dll.
}

// function to create a node
// with the value being set as the data
// that is passed as the parameter,
// and initializing its left and right children to NULL
node* newNode(int data)
{
node* new_node = new node;
new_node->data = data;
new_node->left = new_node->right = NULL;
return (new_node);
}

// to print, traverse over the doubly linked list
// from the left node to the right node.
void printDLL(node *node)
{
while (node!=NULL)
{
cout << node->data << " "; node = node->right;
}
}

int main()
{
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);

cout << "\nConverted Doubly Linked List:\n";

return 0;
}
```

### Output

```Converted Doubly Linked List:
25 12 30 10 36 15``` ### JAVA

```// Class for a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
class Node
{
int data;
Node left, right;

public Node(int data)
{
this.data = data;
left = right = null;
}
}

class BinaryTree
{
Node root;

// static variable to
// store the node visited previously.
// initialize it to null
static Node prev = null;

// function to recursively convert the binary tree
// whose root has been passed to it as a parameter
// to a doubly linked list, whose head as also been passed
// to it as a parameter.
void ConvertBT(Node root)
{
// Base case
if (root == null)
return;

// convert recursively the left subtree
// into dll.
ConvertBT(root.left);

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

// convert recursively the right subtree
// into dll.
ConvertBT(root.right);
}

// to print, traverse over the doubly linked list
// from the left node to the right node.
void printDLL(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.right;
}
}

public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(12);
tree.root.right = new Node(15);
tree.root.left.left = new Node(25);
tree.root.left.right = new Node(30);
tree.root.right.left = new Node(36);

tree.ConvertBT(tree.root);

}
}
```

### Output

```Converted Doubly Linked List:
25 12 30 10 36 15``` ### Python

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

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

def convert(self, root):

# Base case
if root is None:
return

# convert recursively the left subtree
# into dll.
self.convert(root.left)

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

# convert recursively the right subtree
# into dll.
self.convert(root.right)

def ConvertBT(root):
# function to recursively convert the binary tree
# whose root has been passed to it as a parameter
# to a doubly linked list, whose head as also been passed
# to it as a parameter.
converter = BtoDll()
return converter.convert(root)

# to print, traverse over the doubly linked list
# from the left node to the right node.

if __name__ == "__main__":

root = Node(10)
root.left = Node(12)
root.right = Node(15)
root.left.left = Node(25)
root.left.right = Node(30)
root.right.left = Node(36)

```

### Output

```Converted Doubly Linked List:
25 12 30 10 36 15```

Time Complexity: O(n), where n is the number of nodes, as we are applying simple in order traversal. 