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.
// head --> Pointer to head node of created doubly-linked
// list
void BinaryTree2DoubleLinkedList(nod* root, nod** head)
{
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.
BinaryTree2DoubleLinkedList(root->Lft, head);
// we will now have to change this node into something else.
if (pre== NILL)
*head = root;
else {
root->Lft = prev;
prev->Rt = root;
}
pre= root;
// finally, we have to change the right subtree.
BinaryTree2DoubleLinkedList(root->Rt, head);
}
/* 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.
nod* head = NILL;
BinaryTree2DoubleLinkedList(root, &head);
// Print the converted list
printList(head);
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.
// head --> Pointer to head nod of created doubly-linked
// list
void BinaryTree2DoubleLinkedList(nod* root, nod** head)
{
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.
BinaryTree2DoubleLinkedList(root->Lft, head);
// we will now have to change this node into something else.
if (pre== NILL)
*head = root;
else {
root->Lft = prev;
prev->Rt = root;
}
pre= root;
// finally, we have to change the right subtree.
BinaryTree2DoubleLinkedList(root->Rt, head);
}
/* 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.
nod* head = NILL;
BinaryTree2DoubleLinkedList(root, &head);
// Print the converted list
printList(head);
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;
// head --> Pointer to head nod of created doubly linked list
Nod head;
// 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
// to Doubly Linked List
// root --> Root of Binary Tree
void BinaryTree2DoubleLinkedList(Nod root)
{
// Base case
if (root == NILL)
return;
// Recursively convert Left subtree
BinaryTree2DoubleLinkedList(root.Lft);
// Now convert this nod
if (pre== NILL)
head = root;
else
{
root.Lft = prev;
prev.Rt = root;
}
pre= root;
// Finally, convert the right subtree
BinaryTree2DoubleLinkedList(root.Rt);
}
/* 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.
Tree.BinaryTree2DoubleLinkedList(tree.root);
// Print the converted List
tree.printList(tree.head);
}
}
Output:
