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: