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

  • 0

    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.

    depthLinkedListArray[0] = (10)

    depthLinkedListArray[1] = (6,30)

    depthLinkedListArray[2] = (3,8,25,40)

    depthLinkedListArray[3] = (1,2,7,9)

    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;


    • 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
            tDNLL->nextDepthLevelList = makeTreeDepthNode(tNode); 
        } else{
            //Already visited, so just add nth depth level nod in nth node linked list 
            addNodeInDepthList(tDNLL->nextDepthLevelList->depthNodeList, tNode);
        makeListForEachDepth(tDNLL->nextDepthLevelList, tNode->left);
        makeListForEachDepth(tDNLL->nextDepthLevelList, tNode->right);
        return tDNLL->nextDepthLevelList;


    Depth[ 0 ] - 10

    Depth[ 1 ] - 6 30

    Depth[ 2 ] - 3 8 25 40

    Depth[ 3 ] - 1 2 7 9

Log in to reply

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