Given the root of the binary tree and a pointer to any random node in that tree, the objective is to print all the nodes at ‘k’ distance from the given random node

#include <stdio.h>

struct TreeNode
{
  TreeNode *left, *right;
  int el;

  explicit TreeNode(int _el) : left(NULL), right(NULL), el(_el) {}
};

typedef TreeNode* Tree;

/*
  prints all the descendent nodes which are k distance from t
*/

void printNodes(Tree t, int k) 
{
  if (t == NULL || k < 0) {
     return;
  };

  if (k == 0)  {
    printf ("%d", t->el);  
  }
  else {
    printNodes(t->left, k - 1);
    printNodes(t->right, k - 1);
  }
}

/*
  prints all the nodes which are k distance from the given node n
  returns the distance of t from n
*/

int printNodes(Tree t, TreeNode *n,  int k) 
{
  if (t == NULL) return -1;

  if (t == n) {
    printNodes(t, k);  
    return 0;
  }

  int d;

  if (t->left) {
    d = printNodes(t->left, n, k);

    if (d >= 0) {
      d++;

      if (d == k) {
        printf("%d", t->el);  
      }
      else {
        printNodes(t->right, k - d - 1);  
      }
      return d;
    }
  }

  if (t->right) {
    d = printNodes(t->right, n, k);

    if (d >= 0) {
      d++;
      if (d == k) {
        printf("%d", t->el);  
      }
      else {
        printNodes(t->left, k - d - 1);  
      }
      return d;
    }
  }

  return -1;
}

/*
  Example Tree:

          1
       /    \
      2      3
     / \    /  \
    4   5  6    7
   /     \     / 
  8       9   10

*/

Tree newTree() 
{
  TreeNode *root = new TreeNode(1);
  root->left = new TreeNode(2);
  root->right = new TreeNode(3);
  root->left->left = new TreeNode(4);
  root->left->right = new TreeNode(5);
  root->right->left = new TreeNode(6);
  root->right->right = new TreeNode(7);
  root->left->left->left = new TreeNode(8);
  root->left->right->right = new TreeNode(9);
  root->right->right->left = new TreeNode(10);

  return root;
}

int main(int argc, char const *argv[])
{
  Tree t  = newTree();
  printNodes(t, t->left->right->right, 4); //prints nodes which are 4 distance away from 9  which are (8, 3)
  printf("\n");
  printNodes(t, t, 3); //prints nodes which are 3 distance away from 1  which are (8, 9, 10)
  printf("\n");
  printNodes(t, t->left->right, 4); //prints nodes which are 4 distance away from 5  which are (6, 7)
  printf("\n");
  return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s