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->null

We 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 depthlist = NULL;//list to store set of all linked listresult = NULL; list.push(tree) while(!list.empty()){// push linked list of nodes at current level// to the result listresult.push(list);//make current level as the parent levelparent = list; list.clear();// add all the childs of nodes at current level// to the linked listfor(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.