CareerCup

I am considering default implementation of Binary tree. Parent node is not given.
Using an extra class:

Pair {
		Node node;
		int distance; // To get upwards distance from given node = (depth - distance) .
	}
Step 1. int depth = 0; // After this step it will hold depth of node.
Start from root and traverse path from root to given node (source node), and create a object of Pair(parentNode, depth++)) and add it in a Queue of size K.
If Queue is full before reaching the node (because depth can be larger than K) than remove one node from rear to make space and new node at front.

After this step Queue will hold all nodes and distance upwards at K or less distance from given node.

Queue result; //This will be output.
Step 2: Now find all upward nodes.
     while (Queue ! = NULL){
	 Pair pair  = parentQueue.dequeue();
	 int i = depth - pair.diatance;
	 if( i = K){
             result.add(pair.node);
	 }
         perfrom findKthNodesDownwards(givenNode, pair.node, K - i)
       }

Step 3: Find all downward nodes.
	findKthNodesDownwards(givenNode, null, K)



void findKthNodesDownwards(Node givenNode, Node node , int k)    
{
   if(node == NULL || givenNode == node) 
      return;
   if( k == 0 )
   {
      nodes.add(node);
      return ;
   }
   else
   {      
      findKthNodes( node.left, k-1 ) ;
      findKthNodes( root.right, k-1 ) ;
   }
}

parent pointers available ?

store tree as graph and find the distance from the node to other nodes using graph algorithm.

mark every node as a binary number,

root -> 1
left node to root -> 10
right node to root -> 11
after that -> 100-101 and 110-111

.. and so on, we will have a tree of binary numbers.

now suppose we want to know distance between '100' and '1011', follow these steps,

1. '100' would be at 'level 2' and '1011' at 'level 3'. Parent of '1011' would be '101' and it's distance '1011' would be '1'. We now have to fine distance between 100 and 101.

2. XOR '100' and '101' => '001'. Position of left most '1' in '001' gives distance of common ancestor. In this case it is '1'.

3. Distance between 100 and 1011 would be 2 * 'common ancestor distance' + ( 1011 <-> 101 distance). which is 2*1 + 1 = 3

So 3 is the distance. This way we can calculate all the distances.

here's the pseudo code of an approach I can think of:

void getAllNodesAtk(node *q, int k, <the list of nodes so far> l {
if(q == NULL) {
return;
}

if(k == 0) {
l union {q} and return;
}

getAllNodesAtk(q->left, k-1, l)
getAllNodesAtk(q->right, k-1, l)
}

2 times 2 variations == 4 combinations exist for this problem.

2 choices
========
You can be given a key (must find the node) or given reference to the node (can access the node in question directly).

2 choices
========
Parent pointers available or not.


What does the original poster want code for?

#include<iostream>
using namespace std;

struct Node
{
    int data;
    Node *left;
    Node *right;
    int visit;
};

Node * createNode(int data)
{
    Node * n= new Node();
    n->data=data;
    n->left=NULL;
    n->right=NULL;
    n->visit=0;
    return n;
}

void preorder(Node *root)
{
    if(root==NULL)
        return;
    cout<<root->data<<" ";
    preorder(root->left);
    preorder(root->right);
}


void distantNodes(Node *root,int k)
{
    if(root==NULL || k<0 || root->visit==1)
        return;
    else if(k==0 && root->visit!=1)
    {
        cout<<root->data<<endl;
        root->visit=1;
        return;
    }
    distantNodes(root->left,k-1);
    distantNodes(root->right,k-1);
}


int distantNodesp(Node *root,int data,int k,int *flag)
{
    if(root==NULL || *flag==1)
        return -1;


    if(root->data==data)
    {
        *flag=1;

        distantNodes(root,k);
        root->visit=1;
        return k-1;
    }
    else
    {
        int l=distantNodesp(root->left,data,k,flag);
        if(*flag==1)
        {
            distantNodes(root,l);
            root->visit=1;
            return l-1;
        }

        int r=distantNodesp(root->right,data,k,flag);
        if(*flag==1)
        {
            distantNodes(root,r);
            root->visit=1;
            return r-1;
        }

    }

}

int main()
{
    Node *root=createNode(3);
    root->left=createNode(4);
    root->right=createNode(5);
    root->right->left=createNode(10);
    root->left->left=createNode(6);
    root->left->right=createNode(7);
    root->left->left->left=createNode(8);
    root->left->left->right=createNode(9);
    root->left->right->left=createNode(11);
    root->left->right->right=createNode(12);
    root->left->right->right->left=createNode(15);
    root->left->right->left->left=createNode(13);
    root->left->right->left->right=createNode(14);
    root->left->left->left->left=createNode(16);
    root->left->left->left->right=createNode(17);
    root->left->right->left->right->left=createNode(18);
    root->left->right->left->right->right=createNode(19);
    root->left->right->left->right->left->left=createNode(20);
    root->left->right->left->right->left->right=createNode(21);
    //preorder(root);
    int flag=0;
    distantNodesp(root,11,3,&flag);
    return 0;
}

Correct me if my solution is wrong .

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node{
    int data;
    struct node *left,*right;
};
struct node* newnode(int data)
{
    struct node* node=(struct node*)malloc(sizeof(struct node));
    node->data=data;
    node->left=node->right=NULL;
}
void printNodes(struct node *root,int level)
{
    if(root==NULL)
        return ;
    if(!level)
        cout<<root->data<<endl;
    printNodes(root->left,level-1);
    printNodes(root->right,level-1);
}
int main()
{
    struct node* root=newnode(10);
    root->left=newnode(20);
    root->right=newnode(30);
    root->left->left=newnode(40);
    root->left->right=newnode(50);
    root->right->left=newnode(100);
    printNodes(root,2);
    return 0;
}