[AMAZON]printKDistanceNodes
- You are given a function printKDistanceNodes
which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.
Example:
Sample Input:
Root node: 5
Given start node: 8
Distance (K): 1
Sample Output:
5
6
9
Printing Downwards Path ->
ReplyDeletefunc(root,p,k)
{
if(!root || !p ) return;
if(k==0) print(root->data);
else{ func(root,p->left,k-1);
func(root,p->right,k-1);
}
}
Printing Upwards Path and inverted-V type paths : -
we can do inorder DFS to find the node and keep track of depth,
if node is found,it contains nodes from root to p in stack.
We can pop every node from stack and for ith node popped from stack,call (k-i)distance downwards nodes recursively in the other subtree.
Please check.
typedef struct node
ReplyDelete{
int data;
struct node *left;
struct node *right;
}node;
void printkdistanceNodeDown(node *n, int k)
{
if(!n)
return ;
if(k==0)
{
printf("%d\n",n->data);
return;
}
printkdistanceNodeDown(n->left,k-1);
printkdistanceNodeDown(n->right,k-1);
}
void printkdistanceNodeDown_fromUp(node* target ,int *k)
{
if(!target)
return ;
if(*k==0)
{
printf("%d\n",target->data);
return;
}
else
{
int val=*k;
printkdistanceNodeDown(target,val-1);
}
}
int printkdistanceNodeUp(node* root, node* n , int* k)
{
if(!root)
return 0;
if(root->data==n->data)
return 1;
int pl=printkdistanceNodeUp(root->left,n,k);
int pr=printkdistanceNodeUp(root->right,n,k);
if(pl )
{
(*k)--;
if(*k==0)
printf("%d\n",root->data);
else
printkdistanceNodeDown_fromUp(root->right,k);
return 1;
}
if(pr )
{
(*k)--;
if(*k==0)
printf("%d\n",root->data);
else
printkdistanceNodeDown_fromUp(root->left,k);
return 1;
}
return 0;
}
void printkdistanceNode(node* root, node* n , int k )
{
if(!root)
return ;
int val=k;
printkdistanceNodeUp(root,n,&k);
printkdistanceNodeDown(n,val);
}
caller function : printkdistanceNode(root,n,k);
output will print all the nodes at a distance k from given node upward and downward.
@Anonymous please explain your approach..
ReplyDeleteOnce we find the the given node ,
Delete1>we traverse forward to find all k distance nodes.That is easy.
2>also we traverse backward k distance to find k distance node .
Please note : if we traverse backward and value is less than k for any backward node then we have to traverse down from that node opposite side from where it is coming(i.e if traverse backward is from left subtree than we have to traverse right ).
though my solution doesnt print o/p as desired FORMAT as asked but it prints ALL k distance node from a given node.
check this code with long binary tree .
@admin : i hope this explaination helps.
good collections of question :)
This comment has been removed by the author.
ReplyDelete