Home Practice Programming Algorithm to create linked list of nodes at each depth in Binary...

Algorithm to create linked list of nodes at each depth in Binary tree

Here we are given a binary tree, and we have to design an algorithm from scratch, which will create a linked list of all nodes at each depth. Let’s understand what this means with the following example.

Ex->                          2
                            /   \          
                           5     7
                         /  \   /  \
                        9   8  1    3

Here, we have depth 3, so we will have 3 linked list:
1) 2->N
2) 5->7->N
3) 9->8->1->3->N

Algorithm

We will use the concept of Breadth-First Search here. We will go at every depth, store all the elements at a particular depth in the linked list, and then move to the next depth.

CPP code for the above problem
#include<bits/stdc++.h>
using namespace std;

queue<int> que;
vector<int > vi[10];

int add_edge(vector<int> tree[], int u, int v){
	tree[u].push_back(v);
}

int find_nodes(vector<int> tree[], int s, vector<int> &visited){

	vector<int> level(10,0);
	que.push(s);
	level[s]=1;
	vi[1].push_back(s);

	while(!que.empty()){			//BFS Logic
		
		int temp = que.front();
		visited[temp] = 1;
		que.pop();

		for(int i=0; i<tree[temp].size();i++){
			if(visited[tree[temp][i]]==0){
				que.push(tree[temp][i]);

				vi[level[temp]+1].push_back(tree[temp][i]);     //push all the nodes at same level into a vector
				level[tree[temp][i]] = level[temp]+1;			//level of current node is = level of its parent + 1;
			}
		}
	}
	
	return 0;
}

int main()
{
 	
 	vector<int> tree[10];
 	vector<int> visited(10,0);

 	add_edge(tree,2,5);
 	add_edge(tree,2,7);
 	add_edge(tree,5,9);
 	add_edge(tree,5,8);
 	add_edge(tree,7,1);
 	add_edge(tree,7,3);

 	find_nodes(tree, 2, visited);

 	int i=1;
 	while(!vi[i].empty()){
 		cout<<"at depth "<<i<<" nodes = ";
 		
 		for(int j=0; j<vi[i].size();j++)
 			cout<<vi[i][j]<<" ";

 		cout<<endl;
 		i++;
 	}

	return 0;
}

Output:
at depth 1 nodes = 2 
at depth 2 nodes = 5 7 
at depth 3 nodes = 9 8 1 3
Time Complexity

The time complexity of the above algorithm will be the same as that of BFS O(N), where N is the total number of edges in a tree.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Subscribe to our weekly newsletter

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

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

Books recommendation for interview preparation