Given a binary tree, we have to design an algorithm that will create a linked list of all the nodes at each depth or level. For example, if we have a tree with depth D, then there will be D different linked lists.
Input Tree:
1 level 3
/ \
2 3 level 2
/ \ / \
4 5 6 7 level 1
Output:
1->null
2->3->null
4->5->6->7->nullWe will do the modified Breadth-First Traversal of a given tree. With this modified implementation we will iterate through every level/depth starting from the root (level1, level 2, level3 …), and each level we will create the linked list of the nodes and store linked list created at each level to a result list. Note, the result list will store all linked lists of nodes at each level.
Algorithm
CreateLinkedList(tree){
if(tree == NULL)
return
//linked list to store all nodes at each depth
list = NULL;
//list to store set of all linked list
result = NULL;
list.push(tree)
while(!list.empty()){
// push linked list of nodes at current level
// to the result list
result.push(list);
//make current level as the parent level
parent = list;
list.clear();
// add all the childs of nodes at current level
// to the linked list
for(node in parent)
if(node->left!=NULL)
list.push(node->left)
if(node->right!=NULL)
list.push(node->right)
}
display(result)
}Implementation of the above algorithm in CPP
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
Node *left,*right;
int data;
public:
Node(int x){
data = x;
left = NULL;
right = NULL;
}
};
typedef list<Node *> lst;
typedef vector<list<Node *> > vec_list;
int display_list(vec_list result)
{
vec_list::iterator it_vec;
lst::iterator it_lst;
cout<<"Linked List of all the nodes at each level:"<<endl;
//iterate through all the linked list created
for(it_vec = result.begin(); it_vec != result.end(); it_vec++)
{
//iterate through linked list at current depth/level and print all the elements.
for(it_lst = (*it_vec).begin(); it_lst != (*it_vec).end(); it_lst++ )
cout<<(*it_lst)->data<<"->";
cout<<"NULL"<<endl;
}
return 0;
}
int level_order_traversal(Node *tree)
{
vec_list result; //A vector to Linked list to store linked list at each level
lst level; //Linked list of all nodes at each level
level.push_back(tree);
while(!level.empty())
{
result.push_back(level); //move the linked list of current level to the linked list vector
list<Node *> parent = level; //make current linked list as the parent list.
level.clear(); //empty the linkedlist at current level
lst::iterator it;
//store all nodes at next level into the linked list.
for(it = parent.begin();it!=parent.end();it++)
{
if((*it)->left != NULL)
level.push_back((*it)->left);
if((*it)->right != NULL)
level.push_back((*it)->right);
}
}
display_list(result);
return 0;
}
int main()
{
Node *tree = new Node(1);
tree->left = new Node(2);
tree->right = new Node(3);
tree->left->left = new Node(4);
tree->left->right = new Node(5);
tree->right->left = new Node(6);
tree->right->right = new Node(7);
level_order_traversal(tree);
return 0;
}
Output
Linked List of all the nodes at each level: 1->NULL 2->3->NULL 4->5->6->7->NULL
Time Complexity
The time complexity of the above algorithm is O(N), where N is the number of nodes the given tree because of all we are doing to traversing through each node of the given tree. All the other operations will take constant O(1) time.