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);