Print all nodes that are at distance k from a leaf node

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here the meaning of distance k from a leaf means k levels higher than a leaf node.
For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.

           [1]
          /   \
       [2]     [3]
      /  \     /  \
    [4]  [5] [6]  [7]
    /
  [8]
Here Output should be 1, and 2 for K=2 as both are at 2 distance from leaf nodes.
1 is at K=2 distance from 5 and  2 is K=2 distance from 8.


Method 1)

We are setting some arbitrary large number as height.
with each associated node, will keep this height and decrements it.

eg.
Height[1000]=1
Height [999]=2
Height [998]=4
Height [997]=8
Height [998]=5
Height [999]=3
Height [998]=6
Height [998]=7

When we encounter a node which is leaf (ie. No left no right Sub tree)
we print Height [length+k];

say here

For Node 8K distance node is= 2
For Node 5K distance node is= 1
For Node 6K distance node is= 1

Now think for algorithm on ur own :
else see working code at http://ideone.com/htifVi

Code :

#include <iostream>
using namespace std;
#define MAX_HEIGHT 1000

struct Node
{
    int key;
    Node *left, *right;
};

Node* newNode(int key)
{
    Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return (node);
}

 void kDistantFromLeafUtil(Node* node, int height[], int pathLen, int k)
{
    if (node==NULL) return;

     height[pathLen] =  node->key;
    pathLen--;

 if(node->left == NULL && node->right == NULL){
    cout <<"For Node "<<node->key <<"K distance node is= "<< height[pathLen+k+1] << " "<<endl;
    return;
}
    kDistantFromLeafUtil(node->left, height,  pathLen, k);
    kDistantFromLeafUtil(node->right, height,  pathLen, k);
}

void printKDistantfromLeaf(Node* node, int k)
{
    int height[MAX_HEIGHT];
    bool visited[MAX_HEIGHT] = {false};
    kDistantFromLeafUtil(node, height, 1000, k);
}

int main()
{
    Node * root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->right = newNode(8);
    printKDistantfromLeaf(root, 2);

    return 0;
}

Method 2) Instead decrementing pathLen we can think for approch where we can increment pathLen in order to decrease memory usage.

Changes required

void kDistantFromLeafUtil(Node* node, int height[], int pathLen, int k)
{
    if (node==NULL) return;

    height[pathLen] =  node->key;
    pathLen++;
//SEE CHANGES

 if(node->left == NULL && node->right == NULL){
    cout <<"For Node "<<node->key <<"K distance node is= "<< height[pathLen-k-1] << " "<<endl;
// SEE CHANGES
    return;
}
    kDistantFromLeafUtil(node->left, height,  pathLen, k);
    kDistantFromLeafUtil(node->right, height,  pathLen, k);
}

IN  void printKDistantfromLeaf(Node* node, int k){}
kDistantFromLeafUtil(node, height, 0, k);
Labels: , , , ,