C program to convert a Binary Tree into a Singly Linked List by Traversing Level by Level

In this article, we are going to see how to convert a binary tree into a single link list by traversing level-wise?
Submitted by Radib Kar, on January 07, 2019

Problem statement: Write a C program to convert a binary tree into a single linked list by traversing level-wise.

Example:

The above binary tree is converted to 2 → 7 → 5 → 2 → 6 → 9 → 5 → 11 → 4 → NULL

Solution

Building a linked list - Setting the first node as Head and then appending other nodes.
Traversing & displaying a single link list.
Building a tree & level order traversal of a tree.

Algorithm:

Assign the root value as head node value in linked list.
Do level-order traversal
For each tree node create a single linked list node and append it to the linked list.
Display the single linked list.

How the tree is converted to the single list...

Let’s do solve the above example.

Root=2;
Queue status: 2
----------------------------------------------------

1^st iteration
Queue not empty
Queue front is 2
Head is null, thus head is 2
Linked list up to now:2->NULL
Pop 2
Push: 2->left(7) & 2->right(5)
Queue status: 7, 5
----------------------------------------------------

2^nd iteration
Queue not empty
Queue front is 7
Head is not null, thus append 7
Linked list up to now:2->7->NULL
Pop 7
Push: 7->left(2)& 7->right(6)
Queue status: 5, 2, 6
----------------------------------------------------

3^rd iteration
Queue not empty
Queue front is 5
Head is not null, thus append 5
Linked list up to now:2->7->5->NULL
Pop 5
Push: 5->right (9) only (5->left is NULL)
Queue status: 2, 6, 9 
----------------------------------------------------

4^th iteration
Queue not empty
Queue front is 2
Head is not null, thus append 2
Linked list up to now:2->7->5->2->NULL
Pop 2
Push: Nothing ( both child are NULL)
Queue status: 6, 9 
----------------------------------------------------

5^th iteration
Queue not empty
Queue front is 6
Head is not null, thus append 6
Linked list up to now:2->7->5->2->6->NULL
Pop 6
Push: 6->left(5) and 6->right(11)
Queue status: 9, 5, 11
----------------------------------------------------

6^th iteration
Queue not empty
Queue front is 9
Head is not null, thus append 9
Linked list up to now:2->7->5->2->6->9->NULL
Pop 9
Push: 9->left(4) only (right child NULL)
Queue status: 5, 11, 4
----------------------------------------------------

7^th iteration
Queue not empty
Queue front is 5
Head is not null, thus append 5
Linked list up to now:2->7->5->2->6->9->5->NULL
Pop 5
Push: Nothing (both child NULL)
Queue status: 11, 4 
----------------------------------------------------

8^th iteration
Queue not empty
Queue front is 11
Head is not null, thus append 11
Linked list up to now:2->7->5->2->6->9->5->11->NULL
Pop 11
Push: Nothing (both child NULL)
Queue status: 4 
----------------------------------------------------

8^th iteration
Queue not empty
Queue front is 4
Head is not null, thus append 4
Linked list up to now: 2->7->5->2->6->9->5->11->4->NULL
Pop 4
Push: Nothing (both child NULL)
Queue status: empty queue
----------------------------------------------------

Iteration stops
So final link list is: 2->7->5->2->6->9->5->11->4->NULL

C implementation to to convert a Binary Tree into a Singly Linked List by Traversing Level by Level

#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class tree{    
	public:
		int data;
		tree *left;
		tree *right;
};

class sll{
    public:
    int data;
    sll* next;
};

sll* creatnode(int d){ //create node for single linked list
	sll* temp=(sll*)malloc(sizeof(sll));
	temp->data=d;
	temp->next=NULL;
	return temp;
}

void display(sll* head){
	sll* current=head; // current node set to head

	printf("displayig the converted list...\n");
	while(current!=NULL){ //traverse until current node isn't NULL
	    if(current->next)
		printf("%d->",current->data);
		else
		printf("%d->NULL\n",current->data);
		current=current->next; // go to next node
	}
}

sll* flatten(tree* root)
{
	//Declare queue using STL 
	sll* head=NULL,*tempL;
	queue<tree*> q;
	//enqueue the root
	q.push(root);
	vector<int> store;

	tree* temp;
	//do the level order traversal & build single linked list
	while(!q.empty()){
		//dequeue
		temp=q.front();
		q.pop();
		if(head==NULL){//for inserting first node
		    head=creatnode(temp->data);
		    tempL=head;
		}
		else{//for inserting rest of the nodes
		    tempL->next=creatnode(temp->data);
		    tempL=tempL->next;
		}
		
		// do level order traversing
		if(temp->left)//for left child
			q.push(temp->left);
		if(temp->right)//for right child
			q.push(temp->right);
		
	}
	
	
	return head;

}

tree* newnode(int data)  // creating new node for tree
{ 
	tree* node = (tree*)malloc(sizeof(tree)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 

	return(node); 
} 


int main() 
{ 
	//**same tree is builted as shown in example**
	cout<<"same tree is built as shown in example\n";
	tree *root=newnode(2); 
	root->left= newnode(7); 
	root->right= newnode(5); 
	root->right->right=newnode(9);
	root->right->right->left=newnode(4);
	root->left->left=newnode(2); 
	root->left->right=newnode(6);
	root->left->right->left=newnode(5);
	root->left->right->right=newnode(11);

	cout<<"converting the tree into a single link list...\n";
	cout<<"by traversing the tree level-wise\n";
	sll* head=flatten(root);
	//displaying the list built from the tree
	display(head);

	return 0; 
}

Output

same tree is built as shown in example 
converting the tree into a single link list...
by traversing the tree level-wise
displayig the converted list...
2->7->5->2->6->9->5->11->4->NULL

Comments and Discussions!

Top MCQs

Top Programs/Examples