Nodes At a Distance K From a Given Node

#1

I am trying to implement this program after watching the video but i am not getting the correct answer, can you please tell me where I am making a mistake? My code is : https://ide.codingblocks.com/s/217894

#2

My code is : https://ide.codingblocks.com/s/217893 Acn you tell me where I am making a mistake?

#3

@gourav the seems to be some mistake link contains code for some other problem.

#4

@gourav ignore the above message,Hey! I am assuming your logic to read tree is right,
in printAtKdistance function when, root==target, you are calling percolate and are passing, k, you should be passing k-1.
percolateDown(root,k-1);
If this resolves your doubt mark it as resolved.

#5

@Abhinav2604 I am still not getting right answer.

#6

@gourav

//Nodes At A Distance K From a Given Node
#include<iostream>
#include<queue>
using namespace std;
class node
{
	public:
	int data;
	node *left, *right;
	node(int data) 
	{
		this->data = data;
		left = right = NULL;	
	}	
};
node *buildTree()
{
	int data;
	cin>>data;
	if(data==-1)
		return NULL;
	node *root = new node(data);
	root->left = buildTree();
	root->right = buildTree();
    return root;
}
void percolateDown(node *root,int k)
{
	if(root==NULL || k<0)
		return ;
		
	if(k==0)
	{
		cout<<root->data<<" ";
		return;	
	}
	
	percolateDown(root->left,k-1);
	percolateDown(root->right,k-1);

}
int printAtDistanceK(node *root,node *target,int k)
{
	if(root==NULL)
		return -1;
	if(root==target)
	{
		percolateDown(root,k);
		return 1;
	}
	int left = printAtDistanceK(root->left,target,k);
	int right = printAtDistanceK(root->right,target,k);

	if(left!=-1)
	{
		if(left==k)
			cout<<root->data<<" ";
		percolateDown(root->right,k-left-1);       // do not go in the tree from which you came 
		return left+1;
	}
	
    if(right!=-1)
	{
		if(right==k)
			cout<<root->data<<" ";
		percolateDown(root->left,k-right-1);
		return right+1;
	} 
	return -1;
}
int main()
{
	node *root = buildTree();
	node *target = root->left->right->right;
    cout<<target->data<<" ";
	printAtDistanceK(root,target,3);
	return 0;
}