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.