CareerCup

Assumptions : There is no duplicate data in BST
The following code will print all the k distance node from a given node in unsorted order.

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

typedef struct node * Tree;

void printKDistanceDown(Tree root, int k)
{
    if (root == NULL || k<0) {
        return;
    }
    if(k==0)
        printf("%d\t",root->data);
    printKDistanceDown(root->left,k-1);
    printKDistanceDown(root->right,k-1);
}

int printKDistance(Tree root, Tree node, int k)
{
    int n;
    if (root == NULL || k<0)
        return -1;
    if (root == node) 
    {
        printKDistanceDown(node,k);
        return k-1;
    }
    if(root->data > node->data)
    {
        n = printKDistance(root->left,node,k);
        if (n == 0) {
            printf("%d\t",root->data);
        }
        if (n>0) {
            printKDistanceDown(root->right,n-1);
        }
        return n-1;
    }
    else if (root->data < node->data)
    {
        n= printKDistance(root->right,node,k);
        if(n>0)
        {
            printKDistanceDown(root->left,n-1);
        }
        if (n==0) {
            printf("%d\t",root->data);
        }
        return n-1;
    }
    else
        return -1;
}

I am not sure if I catch the question, e.g. (in fact, it is a binary, not a BST)

5
4 8
6 9

so , the output is
5,
6,
9
because the distance between all of them and start node 8 is 1, right?

#include <iostream>
using namespace std;

struct TreeNode {
TreeNode(): _left_child(0),_right_child(0),_data(0) {}
TreeNode* _left_child;
TreeNode* _right_child;
int _data;
};

// helper Method to print the node.
// Store it into a data structure if required
void Print(TreeNode* node)
{
if(node) {
cout<<node->_data<<endl;
}
}


void FindKDistanceNode(TreeNode *root, int k)
{
if (!root) return;

if (k == 0) {
Print(root);
} else {
FindKDistanceNode(root->_left_child, k-1);
FindKDistanceNode(root->_right_child, k-1);
}
}


int SearchNode (TreeNode *root, TreeNode *n, int k)
{

if (!root) return -1;

if (root == n) {
// node is found
if(k==0) {
// If distance is zero then print the node itself.
Print(root);
return -1;
} else {
FindKDistanceNode(root->_right_child, k-1);
FindKDistanceNode(root->_left_child, k-1);
return 1; //return 1 which the distance from the node
// searched in the last call. i.e. the parent node.
}

}

int left_count = SearchNode(root->_left_child, n, k);
int right_count = SearchNode(root->_right_child, n, k);

if(left_count>0) {
if((k-left_count) == 0) {
Print(root);
return -1;
} else {
FindKDistanceNode(root->_right_child, k - left_count-1);
return ++left_count; // Going on step in heirarchy. So increase the distance by one.
}
}

if(right_count>0) {
if((k-right_count) == 0) {
Print(root);
return -1;
} else {
FindKDistanceNode(root->_left_child, k - right_count-1);
return ++right_count; // Going on step in heirarchy. So increase the distance by one.
}
}

return -1;
}


/*
* Sample Tree
*
* 12
* 13 10
* 8 2 7 4
*5 15 17 9 22 23 30 1
*
*
* For Child2 i.e. 13 nodes at distance
* K=0 -> 13
* k=1 -> 8, 2, 12
* k=2 -> 5, 15, 17 ,9, 10
* k=3 -> 7, 4
*/


int main(int argc, char** argv)
{
TreeNode* root;

TreeNode child1;
child1._data = 12;

TreeNode child2;
child2._data = 13;

TreeNode child3;
child3._data = 10;

TreeNode child4;
child4._data = 8;

TreeNode child5;
child5._data = 2;

TreeNode child6;
child6._data = 7;

TreeNode child7;
child7._data = 4;

TreeNode child8;
child8._data = 5;

TreeNode child9;
child9._data = 15;

TreeNode child10;
child10._data = 17;

TreeNode child11;
child11._data = 9;

TreeNode child12;
child12._data = 22;

TreeNode child13;
child13._data = 23;

TreeNode child14;
child14._data = 30;

TreeNode child15;
child15._data = 1;



root = &child1;

child1._left_child = &child2;
child1._right_child = &child3;

child2._left_child = &child4;
child2._right_child = &child5;

child3._left_child = &child6;
child3._right_child = &child7;

child4._left_child = &child8;
child4._right_child = &child9;

child5._left_child = &child10;
child5._right_child = &child11;

child6._left_child = &child12;
child6._right_child = &child13;

child7._left_child = &child14;
child7._right_child = &child15;

SearchNode(root, &child2, 2);

return 0;
}

storing that path to node so that it can be back traced for upward nodes.

void PrintKDistanceNodes(Node* root, int distance, int k)
{
	if (root == NULL || distance == 0) return;
	if (distance == k)
	{
		printf("%d\n", root->data);
	}
	--distance;
	PrintDistanceNodes(root->left, distance, k);
	PrintDistanceNodes(root->right, distance, k);
}

void printKDistanceNodes (Node root, Node start, int k){

if(root == null) return;

Do BFS from start node and find the nodes which has distance K, print them.

The other solution:

Distance (Node *node, dist, k, Node *parent, Node *child) {

if (node == NULL)
return;

if (dist == k) {
print (node->data);
return;
}
// Passing parent and child to avoid the same node to be visited again.
if (node->left != child)
Distance (node->left, dist+1, k, node, NULL);

if (node->parent != parent)
Distance (node->parent, dist+1, k, NULL, node);

if (node->right != child)
Distance (node->right, dist+1, k, node, NULL);
}

main () {
Distance (Node *node, 0,k, NULL, NULL);
}

This is not printing in sorted order