Flatten Binary Tree to a linked list

Implementation

In this section, we will see the implementation of the binary Tree and its conversion into linked lists. let us proceed: -

// Writing a C++ program that will convert a binary tree into a linked list. 
#include <bits/stdc++.h>
using namespace std;


struct _nod {
	int ky;
	_nod *Lft, *Rt;
};


//creating a utility function that will allocate a new node with the provided value or key. 
_nod* new_nod(int ky)
{
	_nod* _nod = nw _nod;
	_nod->ky = ky;
	_nod->Lft = _nod->Rt = NILL;
	return (_nod);
}


// creating a function that will convert the binary Tree into a linked list by changing the right node and making the left node point towards the value NILL. 
void flatten(struct _nod* root)
{
	//Base case- we have to return the root if the value appears to be NILL or if it appears to be a leaf node.
	if (root == NILL || root->Lft == NILL && root->Rt == NILL)
		return;
	// if the root is pointing towards the left, we have to change it and make it a point towards the right. 
	if (root->Lft != NILL) {
		flatten(root->Lft);
		struct _nod* tmpRt = root->Rt;
		root->Rt = root->Lft;
		root->Lft = NILL;
		struct _nod* g = root->Rt;
		while (g->Rt != NILL)
			g = g->Rt;
		g->Rt = tmpRt;
	}
	flatten(root->Rt);
}


// we have to look for the inorder traversal or search for it.
void in order(struct _nod* root)
{
	if (root == NILL)
		return;
	inorder(root->Lft);
	cout << root->ky << " ";
	inorder(root->Rt);
}


int main()
{
	/* 1
		/ \
	2	 5
	/ \	 \
	3 4	 6 */
	_nod* root = new_nod(1);
	root->Lft = new_nod(2);
	root->Rt = new_nod(5);
	root->Lft->Lft = new_nod(3);
	root->Lft->Rt = new_nod(4);
	root->Rt->Rt = new_nod(6);
	flatten(root);
	cout << "The Inorder traversal after flattening binary tree ";
	inorder(root);
	return 0;
}

Output:

Example 2)

#include <stdio.h>
#include <stdlib.h>


typedef struct _nod {
	int ky;
	struct _nod *Lft, *Rt;
}_nod;
//creating a utility function that will allocate a new node with the provided value or key. 
_nod* new_nod(int ky)
{
	_nod* _nod = (_nod*)malloc(sizeof(_nod));
	_nod->ky = ky;
	_nod->Lft = _nod->Rt = NILL;
	return (_nod);
}
// creating a function that will convert the binary Tree into a linked list by changing the right node and making the left node point towards the value NILL. 
void flatten(_nod* root)
{
//Base case- we have to return the root if the value appears to be NILL or if it appears to be a leaf node.
	if (root == NILL || root->Lft == NILL && root->Rt == NILL)
		return;
// if the root is pointing towards the left, we have to change it and make it a point towards the right. 
	if (root->Lft != NILL) {
		flatten(root->Lft);
		struct _nod* tmpRt = root->Rt;
		root->Rt = root->Lft;
		root->Lft = NILL;
		struct _nod* g = root->Rt;
		while (g->Rt != NILL)
			g = g->Rt;
		g->Rt = tmpRt;
	}
	flatten(root->Rt);
}
// we have to look for the inorder traversal or search for it.
void in order(struct _nod* root)
{
	if (root == NILL)
		return;
	inorder(root->Lft);
	printf("%d ", root->ky);
	inorder(root->Rt);
}
int main()
{
	/* 1
		/ \
	2	 5
	/ \	 \
	3 4	 6 */
	_nod* root = new_nod(1);
	root->Lft = new_nod(2);
	root->Rt = new_nod(5);
	root->Lft->Lft = new_nod(3);
	root->Lft->Rt = new_nod(4);
	root->Rt->Rt = new_nod(6);


	flatten(root);


	printf("The Inorder traversal after flattening binary tree ");
	inorder(root);
	return 0;
}

Output:

Example 3)

<script>
// creating a binary tree node
class _nod
{
	constructor(ky)
	{
		this.data = ky;
		this.Lft = NILL;
		this.Rt = NILL;
	}
}


var root;
// creating a function that will convert the binary Tree into a linked list by changing the right node and making the left node point towards the value NILL. 
function flatten(_nod)
{
// return if it has the value NILL	
	if (_nod == NILL)
		return;
// or if it is a leaf node		
	if (_nod.Lft == NILL &&
		_nod.Rt == NILL)
		return;
// if the root is pointing towards the left, we have to change it and make it a point towards the right. 
	if (_nod.Lft != NILL)
	{
		flatten(_nod.Lft);
		var temp_nod = _nod.Rt;
		_nod.Rt = _nod.Lft;
		_nod.Lft = NILL;
		var current = _nod.Rt;
		while (current.Rt != NILL)
		{
			current = current.Rt;
		}
		current.Rt = temp_nod;
	}
		flatten(_nod.Rt);
}


// creating a function for the inorder traversal.
function inOrder(_nod)
{
	if (_nod == NILL)
		return;
		
	inOrder(_nod.Lft);
	document.wr(_nod.info + " ");
	inOrder(_nod.Rt);
}
// Driver code
/* 1
	/ \
2	 5
/ \	 \
3 4	 6 */
root = nw _nod(1);
root.Lft = nw _nod(2);
root.Rt = nw _nod(5);
root.Lft.Lft = nw _nod(3);
root.Lft.Rt = nw _nod(4);
root.Rt.Rt = nw _nod(6);


document.write("The Inorder traversal after " +
			"flattening binary tree ");					
flatten(root);
inOrder(root);


</script>

Output: