Print all nodes at distance k from a given node |  ; A binary Tree node ; Recursive function to print all the nodes at distance k in the tree ( or subtree ) rooted with given root . See ; Base Case ; If we reach a k distant node , print it ; Recur for left and right subtrees ; Prints all nodes at distance k from a given target node . The k distant nodes may be upward or downward . This function Returns distance of root from target node , it returns - 1 if target node is not present in tree rooted with root . ; Base Case 1 : If tree is empty , return - 1 ; If target is same as root . Use the downward function to print all nodes at distance k in subtree rooted with target or root ; Recur for left subtree ; Check if target node was found in left subtree ; If root is at distance k from target , print root Note that dl is Distance of root 's left child from target ; Else go to right subtree and print all k - dl - 2 distant nodes Note that the right child is 2 edges away from left child ; Add 1 to the distance and return value for parent calls ; MIRROR OF ABOVE CODE FOR RIGHT SUBTREE Note that we reach here only when node was not found in left subtree ; If target was neither present in left nor in right subtree ; A utility function to create a new binary tree node ; Driver program to test above functions ; Let us construct the tree shown in above diagram
#include <iostream> NEW_LINE using namespace std ; struct node { int data ; struct node * left , * right ; } ; void printkdistanceNodeDown ( node * root , int k ) { if ( root == NULL k < 0 ) return ; if ( k == 0 ) { cout << root -> data << endl ; return ; } printkdistanceNodeDown ( root -> left , k - 1 ) ; printkdistanceNodeDown ( root -> right , k - 1 ) ; } int printkdistanceNode ( node * root , node * target , int k ) { if ( root == NULL ) return -1 ; if ( root == target ) { printkdistanceNodeDown ( root , k ) ; return 0 ; } int dl = printkdistanceNode ( root -> left , target , k ) ; if ( dl != -1 ) { if ( dl + 1 == k ) cout << root -> data << endl ; else printkdistanceNodeDown ( root -> right , k - dl - 2 ) ; return 1 + dl ; } int dr = printkdistanceNode ( root -> right , target , k ) ; if ( dr != -1 ) { if ( dr + 1 == k ) cout << root -> data << endl ; else printkdistanceNodeDown ( root -> left , k - dr - 2 ) ; return 1 + dr ; } return -1 ; } node * newnode ( int data ) { node * temp = new node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } int main ( ) { node * root = newnode ( 20 ) ; root -> left = newnode ( 8 ) ; root -> right = newnode ( 22 ) ; root -> left -> left = newnode ( 4 ) ; root -> left -> right = newnode ( 12 ) ; root -> left -> right -> left = newnode ( 10 ) ; root -> left -> right -> right = newnode ( 14 ) ; node * target = root -> left -> right ; printkdistanceNode ( root , target , 2 ) ; return 0 ; }