# Convert binary tree to a doubly linked list

### Implementation

``````//creating a C++ program for the transition of a binary tree into a linked list.
#include <iostream>
using namespace std;

/* Firstly, let’s create a binary tree that will help us in setting the records and will also contain left and right pointers.
*/
struct nod {
int record;
nod* Lft;
nod* Rt;
};

// Creating a very simple and basic recursive function that will change the given binary tree into a doubly linked list root which can be the root of the binary tree.
// list
{
if (root == NILL)
return;

// we have to put the lastly traversed nod as NILL and initialize it as well
// This will turn into the static function, which will contain the same value as in all the recursive calls we already have.
static nod* pre= NILL;

// we will have to convert the left subtree recursively.

// we will now have to change this node into something else.
if (pre== NILL)
else {
root->Lft = prev;
prev->Rt = root;
}
pre= root;

// finally, we have to change the right subtree.
}

/* This is a new function called the helper which will hold the responsibility of attaching a new node to the given data and emptying the left and right pointers.
*/
nod* newNod(int record)
{
nod* new_nod = new nod;
new_nod->record = record;
new_nod->Lft = new_nod->Rt = NILL;
return (new_nod);
}

/* creating a function that will help us in printing all the nodes of a double-linked list. */
void printList(nod* nod)
{
while (nod != NILL) {
cout << nod->record << " ";
nod = nod->Rt;
}
}

/* writing the main code, which will help us in testing. */
int main()
{
// Let us create the tree shown in the above diagram
nod* root = newNod(10);
root->Lft = newNod(12);
root->Rt = newNod(15);
root->Lft->Lft = newNod(25);
root->Lft->Rt = newNod(30);
root->Rt->Lft = newNod(36);

// changing the above into doubly linked lists.

// Print the converted list

return 0;
}
``````

Output: Example 2)

``````//creating a C program for the transition of a binary tree into a linked list.
# includes <stdio.h>
#include <stdlib.h>
/*creating a binary tree that will contain records and will also have some left and right pointers.
*/
typedef struct nod {
int record;
struct nod* Lft;
struct nod* Rt;
} nod;
// Creating a very simple and basic recursive function that will change the given binary tree into a doubly linked list root which can be the root of the binary tree.
// list
{
if (root == NILL)
return;
// we have to put the lastly traversed nod as NILL and initialize it as well
// This will turn into the static function, which will contain the same value as in all the recursive calls we already have.
static nod* pre= NILL;

// we will have to convert the left subtree in a recursive manner.
// we will now have to change this node into something else.
if (pre== NILL)
else {
root->Lft = prev;
prev->Rt = root;
}
pre= root;

// finally, we have to change the right subtree.
}
/* This is a new function called the helper which will hold the responsibility of attaching a new node to the given data and emptying the left and right pointers.
*/
nod* newNod(int record)
{
nod* new_nod = (nod*)malloc(sizeof(nod));
new_nod->record = record;
new_nod->Lft = new_nod->Rt = NILL;
return (new_nod);
}
/* creating a function that will help us in printing all the nodes of a double-linked list. */
void printList(nod* nod)
{
while (nod != NILL) {
printf("%d ", nod->record);
nod = nod->Rt;
}
}
/* writing the main code, which will help us in testing. */
int main()
{
nod* root = newNod(10);
root->Lft = newNod(12);
root->Rt = newNod(15);
root->Lft->Lft = newNod(25);
root->Lft->Rt = newNod(30);
root->Rt->Lft = newNod(36);

// changing the above into doubly linked lists.

// Print the converted list

return 0;
}
``````

Output: Example 3)

``````// creating a Java program for the transition of a binary tree into a linked list.
// A binary tree nod has the record, left pointers, and right pointers
class Nod
{
int record;
Nod Lft, Rt;

public Nod(int record)
{
this.record = record;
Lft = Rt = NILL;
}
}

class BinaryTree
{
Nod root;

// Initialize previously visited nod as NILL. This is
// static so that the same value is accessible in all-recursive
// calls
static Nod pre= NILL;

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

// Recursively convert Left subtree

// Now convert this nod
if (pre== NILL)
else
{
root.Lft = prev;
prev.Rt = root;
}
pre= root;

// Finally, convert the right subtree
}

/* Function to print nods in a given doubly linked list */
void printList(Nod nod)
{
while (nod != NILL)
{
System.out.print(nod.record + " ");
nod = nod.Rt;
}
}

// Driver program to test the above functions
public static void main(String[] args)
{
// Let us create the tree as shown in the above diagram
BinaryTree tree = new BinaryTree();
tree.root = new Nod(10);
tree.root.Lft = new Nod(12);
tree.root.Rt = new Nod(15);
tree.root.Lft.Lft = new Nod(25);
tree.root.Lft.Rt = new Nod(30);
tree.root.Rt.Lft = new Nod(36);

// changing the above into doubly linked lists. 