Print all nodes that are at distance k from a leaf node | Program to print all nodes which are at distance k from a leaf ; utility that allocates a new Node with the given key ; This function prints all nodes that are distance k from a leaf node path [ ] -- > Store ancestors of a node visited [ ] -- > Stores true if a node is printed as output . A node may be k distance away from many leaves , we want to print it once ; Base case ; append this Node to the path array ; it 's a leaf, so print the ancestor at distance k only  if the ancestor is not already printed  ; If not leaf node , recur for left and right subtrees ; Given a binary tree and a number k , print all nodes that are k distant from a leaf ; Driver code ; Let us create binary tree given in the above example
#include <iostream> NEW_LINE using namespace std ; #define MAX_HEIGHT  10000 NEW_LINE 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 path [ ] , bool visited [ ] , int pathLen , int k ) { if ( node == NULL ) return ; path [ pathLen ] = node -> key ; visited [ pathLen ] = false ; pathLen ++ ; if ( node -> left == NULL && node -> right == NULL && pathLen - k - 1 >= 0 && visited [ pathLen - k - 1 ] == false ) { cout << path [ pathLen - k - 1 ] << " ▁ " ; visited [ pathLen - k - 1 ] = true ; return ; } kDistantFromLeafUtil ( node -> left , path , visited , pathLen , k ) ; kDistantFromLeafUtil ( node -> right , path , visited , pathLen , k ) ; } void printKDistantfromLeaf ( Node * node , int k ) { int path [ MAX_HEIGHT ] ; bool visited [ MAX_HEIGHT ] = { false } ; kDistantFromLeafUtil ( node , path , visited , 0 , 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 -> right -> left -> right = newNode ( 8 ) ; cout << " Nodes ▁ at ▁ distance ▁ 2 ▁ are : ▁ " ; printKDistantfromLeaf ( root , 2 ) ; return 0 ; }