Print all nodes at distance k from a given node | A binary tree node ; Recursive function to print all the nodes at distance k int 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 subtee ; 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 : dl is distance of root 's left child  from target ; Else go to right subtreee and print all k - dl - 2 distant nodes Note : that the right child is 2 edges away from left chlid ; Add 1 to the distance and return value for 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 ; Let us construct the tree shown in above diagram
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def printkDistanceNodeDown ( root , k ) : NEW_LINE INDENT if root is None or k < 0 : NEW_LINE INDENT return NEW_LINE DEDENT if k == 0 : NEW_LINE INDENT print root . data NEW_LINE return NEW_LINE DEDENT printkDistanceNodeDown ( root . left , k - 1 ) NEW_LINE printkDistanceNodeDown ( root . right , k - 1 ) NEW_LINE DEDENT def printkDistanceNode ( root , target , k ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if root == target : NEW_LINE INDENT printkDistanceNodeDown ( root , k ) NEW_LINE return 0 NEW_LINE DEDENT dl = printkDistanceNode ( root . left , target , k ) NEW_LINE if dl != - 1 : NEW_LINE INDENT if dl + 1 == k : NEW_LINE INDENT print root . data NEW_LINE DEDENT else : NEW_LINE INDENT printkDistanceNodeDown ( root . right , k - dl - 2 ) NEW_LINE DEDENT return 1 + dl NEW_LINE DEDENT dr = printkDistanceNode ( root . right , target , k ) NEW_LINE if dr != - 1 : NEW_LINE INDENT if ( dr + 1 == k ) : NEW_LINE INDENT print root . data NEW_LINE DEDENT else : NEW_LINE INDENT printkDistanceNodeDown ( root . left , k - dr - 2 ) NEW_LINE DEDENT return 1 + dr NEW_LINE DEDENT return - 1 NEW_LINE DEDENT root = Node ( 20 ) NEW_LINE root . left = Node ( 8 ) NEW_LINE root . right = Node ( 22 ) NEW_LINE root . left . left = Node ( 4 ) NEW_LINE root . left . right = Node ( 12 ) NEW_LINE root . left . right . left = Node ( 10 ) NEW_LINE root . left . right . right = Node ( 14 ) NEW_LINE target = root . left . right NEW_LINE printkDistanceNode ( root , target , 2 ) NEW_LINE