Home Programming Puzzles Design an algorithm to create a linked list of all the nodes...

Design an algorithm to create a linked list of all the nodes at each depth

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

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here