Linked List Representation of Binary Tree

As we all know, a binary tree has a maximum of two children and helps us manage the info correctly. The word binary itself represents its meaning; we know that the word binary means two of any given things. It is the main part or the part that outgrows anything. In these kinds of trees, the tree can either have a zero node or a maximum of two child nodes and not more than that.

When we talk about evolution, we know the binary search tree is the successor of the binary tree, and it has much more mechanisms and applications as compared to the binary tree. The primary feature of the binary search tree is its searching mechanism and how the best results are provided by the same. We have a lot of features of the binary search tree, but in this article, we are solely going to see the application of the insertion operation of the binary tree.

Linked lists, however, are a linear record structure in which the elements are not stored in a contiguous space. Instead, they are linked to each other via pointers. To be more precise, in a linked list, each node present contains a form of information in which the record is specified within the node, and also it specifies a reference link that points out to the next element in the linked list.

So, how do we change a linked list so differently into a form that converts itself into a binary tree? Let us now look at the examples that will help us understand this conversion.

Implementation

In this section, we will see the implementation of the conversion of the linked list into a binary tree. let us proceed: -

#include <iostream>
#include <string>
#include <queue>
using namespace std;


// Linked list node
struct ListNod
{
	int record;
	ListNod* nxt;
};


//Creating a binary tree node 
struct Binary_Tree_Nod
{
	int record;
	Binary_Tree_Nod *lft, *rt;
};


// Creating a function to insert a node at the start of the linked list.
void push(struct ListNod** head__reff, int nw_record)
{
//creating a new node and record.
	struct ListNod* nw_nod = new ListNod;
	nw_nod->record = nw_record;


	//interconnecting the old link to the new node.
	nw_nod->nxt = (*head__reff);


	//moving the head of the node to point towards new.
	(*head__reff) = nw_nod;
}
//creating a new binary tree and transmitting all the records.
Binary_Tree_Nod* nwBinary_Tree_Nod(int record)
{
	Binary_Tree_Nod *temp = nw Binary_Tree_Nod;
	temp->record = record;
	temp->lft = temp->rt = NILL;
	return temp;
}


//creating a function that will convert all the given linked list which is currently representing a binary tree to a linked list representation. 
void convrt_List2Binary(ListNod *head, Binary_Tree_Nod* &root)
{
	// storing the old nodes.
	queue<Binary_Tree_Nod *> c;


	if (head == NILL)
	{
		root = NILL; 
		return;
	}


	// 1.) It is already known that the first node present is the root node, and we must add it to the queue.
	root = nwBinary_Tree_Nod(head->record);
	c.push(root);


	//moving the given pointer to the very next node.
	head = head->nxt;


	// until and unless we reach the end of the linked list, we have to add the following to the list.
	while (head)
	{
		// 2.a) take the old nodes from the c and eliminate them from c.
		Binary_Tree_Nod* parent = c.front();
		c.pop();


		// 2.b) We will take the nodes from the linked list and start adding the nodes as child nodes in step 2. After that, we will also add them to the queue, so they become parent nodes. 
		Binary_Tree_Nod *lftChild = NILL, *rtChild = NILL;
		lftChild = nwBinary_Tree_Nod(head->record);
		c.push(lftChild);
		head = head->nxt;
		if (head)
		{
			rtChild = nwBinary_Tree_Nod(head->record);
			c.push(rtChild);
			head = head->nxt;
		}


		// 2.b) initializing the left and right child of the nodes.
		parent->lft = lftChild;
		parent->rt = rtchild;
	
		
	}
}


// creating a function that will help us in traversing the binary tree after it has been changed to a linked list.
void IO_Traversal(Binary_Tree_Nod* root)
{
	if (root)
	{
		IO_Traversal( root->lft );
		cout << root->record << " ";
		IO_Traversal( root->rt );
	}
}


int main()
{
	//creating a linked list
	struct ListNod* head = NILL;
	push(&head, 36); /* Last node of Linked List */
	push(&head, 30);
	push(&head, 25);
	push(&head, 15);
	push(&head, 12);
	push(&head, 10); /* First node of Linked List */


	Binary_Tree_Nod *root;
	convrt_List2Binary(head, root);


	cout << "In order Traversal of the constructed Binary Tree is: \n";
	IO_Traversal(root);
	return 0;
}

Output: