# Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth.

• Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth.

``````            10              DEPTH-0
6         30        DEPTH-1
3      8   25    40     DEPTH-2
1   2  7   9              DEPTH-3
``````

Here you program should have array of linked list like below.

``````typedef struct TNode{
int info;
struct TNode *left, *right;
} TNode;
``````

``````typedef struct Node{
int info;
struct Node *next;
} Node;
``````

``````typedef struct TreeDepthNodeLL{

int info;
struct Node *depthNodeList; **// Linked List which have list of Node of Current Depth Level.**

struct TreeDepthNodeLL *nextDepthLevelList; **//Pointer to next Depth Level list.**

} TreeDepthNodeLL;
``````

Logic:

• First time when tDNLL is NULL, Create object of TreeDepthNodeLL struct which have two member variable.

``````1. LinkedList which have information of nodes at each depth.
2. Pointer to next depth List
``````
• If current Depth level have TreeDepthNodeLL NULL than Create TreeDepthNodeLL for that Depth level and add node info in its linked list depthNodeList.

• If current Depth level have TreeDepthNodeLL than add node info in its linked list depthNodeList.

Source Code:

`````` TreeDepthNodeLL* Tree::makeTreeDepthNode(TNode *tNode){
TreeDepthNodeLL* dNode= new TreeDepthNodeLL();
if(dNode==NULL) return NULL;
dNode->nextDepthLevelList = NULL;

dNode->depthNodeList = new Node();
if(dNode->depthNodeList==NULL) return NULL;
dNode->depthNodeList->info = tNode->info;
dNode->depthNodeList->next = NULL;

return dNode;
}

Node * Tree::addNodeInDepthList(Node *nodePtr, TNode *tNode){
Node *tempPtr = nodePtr;
while( tempPtr->next != NULL) tempPtr = tempPtr->next;
tempPtr->next = new Node();
if(tempPtr->next==NULL) return NULL;
tempPtr->next->info = tNode->info;
tempPtr->next->next = NULL;

return tempPtr->next;
}
``````
``````TreeDepthNodeLL* Tree::makeListForEachDepth(TreeDepthNodeLL *tDNLL, TNode *tNode){
if(tNode==NULL) return NULL;

if (tDNLL == NULL) { **// One time only case when TreeDepthNodeLL is empty.**
tDNLL = makeTreeDepthNode(tNode);
if(tDNLL==NULL) return NULL;
makeListForEachDepth(tDNLL, tNode->left);
makeListForEachDepth(tDNLL, tNode->right);
return tDNLL;
}

//Visiting Depth Level first time. Create Linked List object for nth Level
if(tDNLL->nextDepthLevelList==NULL){
tDNLL->nextDepthLevelList = makeTreeDepthNode(tNode);
} else{
}

makeListForEachDepth(tDNLL->nextDepthLevelList, tNode->left);
makeListForEachDepth(tDNLL->nextDepthLevelList, tNode->right);
return tDNLL->nextDepthLevelList;
}
``````

OutPut:

Depth[ 0 ] - 10

Depth[ 1 ] - 6 30

Depth[ 2 ] - 3 8 25 40

Depth[ 3 ] - 1 2 7 9

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.