Find nodes in a binary tree which are at a distance K from a given node

Algorithms 1 Minute

You are given a binary tree and a node in the tree, your task is to find all the nodes in the binary tree which are at a distance K from that node. These nodes can be downwards [descendants of the node] or upwards.

For example: In this image

http://www.cs.mcgill.ca/~jeromew/comp252/images/Binary_tree.png

The nodes that are at a distance 2 from 7 are 5 (6’s left child), 11, 5 (2’s right child).

This is a coding question.

Function prototype:

void PrintKDistanceNode(Node *root, Node *node, int K)

{

}

Published by ranganathg

Published

2 thoughts on “Find nodes in a binary tree which are at a distance K from a given node”

  1. Didn’t see your prototype. My code(printed inorder and preorder so that you can form the tree to see the structure):

    #include
    #include
    #include

    struct node
    {
    struct node *parent;
    struct node *left;
    int data;
    struct node *right;
    };

    void inorder(struct node *);
    void preorder(struct node *);
    struct node * insert(struct node **,int, struct node *);
    void findNodesFromDistance(int, struct node *,int);

    void main()
    {
    int req=13,height,distance;
    int parentList[13][2];
    struct node *q,*nodeToBeFound;

    q=NULL;

    insert(&q,10,NULL);
    insert(&q,5,NULL);
    insert(&q,13,NULL);
    insert(&q,2,NULL);
    insert(&q,8,NULL);
    insert(&q,12,NULL);
    insert(&q,15,NULL);
    insert(&q,1,NULL);
    insert(&q,4,NULL);
    insert(&q,7,NULL);
    insert(&q,9,NULL);
    insert(&q,14,NULL);
    insert(&q,3,NULL);
    insert(&q,6,NULL);

    printf(“Inorder :\n”);
    inorder(q);
    printf(“\nPreorder :\n”);
    preorder(q);
    nodeToBeFound=NULL;

    nodeToBeFound = findElement(5,q);
    findNodesFromDistance(2,nodeToBeFound,nodeToBeFound->data);
    getch();
    }

    struct node * findElement(int data, struct node *q)
    {
    while(q!=NULL)
    {
    if((q)->data==data)
    {
    return q;
    }
    if(q->data>data)
    q=q->left;
    else
    {
    q=q->right;
    }
    }
    }

    void findNodesFromDistance(int num, struct node *q,int nodeData)
    {
    if(q!=NULL)
    {
    if(num==0)
    {
    if((q)->data!=nodeData)
    printf(“\nNode : %d”,(q)->data);
    }
    else
    {
    findNodesFromDistance(num-1,((q)->left),nodeData);
    findNodesFromDistance(num-1,((q)->right),nodeData);
    findNodesFromDistance(num-1,(q)->parent,nodeData);
    }
    }
    }

    struct node * insert(struct node **q,int num, struct node *parent)
    {
    if(*q==NULL)
    {
    *q = (struct node *)malloc(sizeof(struct node));
    (*q)->parent=parent;
    (*q)->left=NULL;
    (*q)->data = num;
    (*q)->right=NULL;

    return *q;
    }
    else
    {

    if(numdata)
    {
    insert(&((*q)->left),num,(*q));
    }
    else
    {
    insert(&((*q)->right),num,(*q));
    }

    return *q;
    }
    }

    void inorder(struct node *q)
    {
    if(q!=NULL)
    {
    inorder(q->left);
    printf(“%d “,q->data);
    inorder(q->right);
    }
    }

    void preorder(struct node *q)
    {
    if(q!=NULL)
    {
    printf(“%d “,q->data);
    preorder(q->left);
    preorder(q->right);
    }
    }

    Reply

Leave a comment