Tuesday, November 20, 2012

Printing all nodes at a given distance from a starting node in a binary tree


#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
return new_node;
};
int printKDistance(node* root,node* start,int k,int *found)
{
if(root)
{
//cout<<root->data<<endl;
if(k==0)
{
cout<<root->data<<endl;
}
else if(root==start || *found==1)
{
*found=1;
printKDistance(root->left,start,k-1,found);
printKDistance(root->right,start,k-1,found);
return 1;
}
else if(*found==0)
{
int ldist = printKDistance(root->left,start,k,found);
//cout<<"ldist="<<ldist<<endl;
int rdist=0;
if(*found==0)
{
rdist = printKDistance(root->right,start,k,found);
}
if((ldist == k || rdist == k) && *found==1)
{
cout<<root->data<<endl;
}
else
{
if(ldist!=0 || rdist!=0)
return ldist>rdist?1+ldist:1+rdist;
}
}
else
{
return 0;
}
}
else
{
return 0;
}
}
int main()
{
struct node* root=createnode(1);
root->left=createnode(2);
root->right=createnode(3);
root->left->right=createnode(4);
root->left->left=createnode(5);
root->right->right=createnode(6);
root->right->left=createnode(7);
root->right->right->left=createnode(8);
//root->right->right->left->left=createnode(10);
root->right->right->right=createnode(10);
int k=2;
//struct node* start = root->right->right->left;
struct node* start = root->right->left;
cout<<"start node="<<start->data<<endl;
cout<<"k="<<k<<endl;
int a=0;
int *found=&a;
printKDistance(root,start,k,found);
}
Output:
start node=7
k=2
Node: 1

No comments:

Post a Comment