CareerCup

w w w . geeksforgeeks. org /archives/ 8615

w w w . geeksforgeeks. org /archives/ 8615

above solution is for root node only. If a node is given then we need to find out the vertical position (v) first, and then traverse the tree again and look for v+k and v-k vertical positions and print

The solution is there in the complete thread.... some one has posted it as comment

#include<stdio.h>
#include<conio.h>
struct node
{
   int d;
   struct node* l;
   struct node* r;
};
struct node* newnode(int data)
{
  struct node* tnode = (struct node*)
                       malloc(sizeof(struct node));
  tnode->d = data;
  tnode->l = NULL;
  tnode->r = NULL;
 
  return(tnode);
}
void K_dist_children(node *nd, int K)
{
// Base case
// The Kth child found
if(K==0)
{
printf("%d\n", nd->d);
return;
}

// K distance node from nd are at
// K-1 distance from children of current node
K_dist_children(nd->l, K-1);
K_dist_children(nd->r, K-1);
}

int K_dist_ancestor(node *cur,node *search,int K)
{
    int n1, n2;
// If the node is found, return back the result
if (cur == search)
{
return K-1;
}



// recursively search for the node in the tree
n1 = K_dist_ancestor(cur->l, search, K);
n2 = K_dist_ancestor(cur->r, search, K);

// PS: n1 & n2 can't be non-(-1) at the same time

// if node found in any of the sub trees
if((n1 == -1) && (n2 == -1))
return -1;

// node found in right subtree
if((n1 == -1))
{
// the current node is at distance K
if(n2 == 0)
printf("%d", cur->d);

// return back the distance
return (n2-1);
}

// node found in left subtree
if((n2 == -1))
{
// the current node is at distance K
if(n1 == 0)
printf("%d", cur->d);

// return back the distance
return (n1-1);
}
}


int main()
{
 
  /* Constructed binary tree is
            1
          /   \
        2      3
      /  \
    4     5
  */

  int n;
  struct node *root = newnode(1);
  root->l       = newnode(2);
  root->r      = newnode(3);
  root->l->l  = newnode(4);
  root->l->r = newnode(5);
  root->l->r->l = newnode(6);
  root->l->r->r= newnode(7);
  
n=K_dist_ancestor(root,root->l,3);
 
	// Print the children at distance K
	K_dist_children(root->l,3);
  
  getchar();
  getchar();
  return 0;
}

A simple BFS should solve the problem.

I think level order traversal should solve the issue. Keep traversing the tree level by level and put a marker to separate levels.

public int PrintNodesAtKDistance(Node root, int requiredNode, int iDistance)
{
if ((root == null) || (iDistance < 0))
return -1;

int lPath = -1, rPath = -1;

if(root.value == requiredNode)
{
PrintChildNodes(root, iDistance);
return iDistance - 1;
}

lPath = PrintNodesAtKDistance(root.left, requiredNode, iDistance);
rPath = PrintNodesAtKDistance(root.right, requiredNode, iDistance);

if (lPath > 0)
{
PrintChildNodes(root.right, lPath - 1);
return lPath - 1;
}
else if(lPath == 0)
{
Debug.WriteLine(root.value);
}

if(rPath > 0)
{
PrintChildNodes(root.left, rPath - 1);
return rPath - 1;
}
else if (rPath == 0)
{
Debug.WriteLine(root.value);
}

return -1;
}

public void PrintChildNodes(Node aNode, int iDistance)
{
if (aNode == null)
return;

if(iDistance == 0)
{
Debug.WriteLine(aNode.value);
}

PrintChildNodes(aNode.left, iDistance - 1);
PrintChildNodes(aNode.right, iDistance - 1);
}