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

19 Jul

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)

{

}

Posted by on July 19, 2012 in Algorithms

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

1. August 10, 2012 at 2:44 pm

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);
}
}

2. August 23, 2012 at 7:43 pm

do with no parent pointer