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;

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.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;
vector<int> visited(10,0);

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.