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 = 2at depth 2 nodes = 5 7at 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.