Find the closest leaf in a Binary Tree | Python program to find closest leaf of a given key in binary tree ; A binary tree node ; A utility function to find distance of closest leaf of the tree rooted under given root ; Base Case ; Return minum of left and right plus one ; Returns destance of the closes leaf to a given key k The array ancestors us used to keep track of ancestors of current node and ' index ' is used to keep track of current index in 'ancestors[i]   ; Base Case ; if key found ; Find closest leaf under the subtree rooted with given key ; Traverse ll ancestors and update result if any parent node gives smaller distance ; if key node found , store current node and recur for left and right childrens ; The main function that return distance of the clses key to key '. It mainly uses recursive function findClosestUtil() to find the closes distance ; Create an arrray to store ancestors Assumption : Maximum height of tree is 100 ; Let us construct the BST shown in the above figure
INT_MAX = 2 ** 32 NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def closestDown ( root ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return INT_MAX NEW_LINE DEDENT if root . left is None and root . right is None : NEW_LINE INDENT return 0 NEW_LINE DEDENT return 1 + min ( closestDown ( root . left ) , closestDown ( root . right ) ) NEW_LINE DEDENT def findClosestUtil ( root , k , ancestors , index ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return INT_MAX NEW_LINE DEDENT if root . key == k : NEW_LINE INDENT res = closestDown ( root ) NEW_LINE for i in reversed ( range ( 0 , index ) ) : NEW_LINE INDENT res = min ( res , index - i + closestDown ( ancestors [ i ] ) ) NEW_LINE DEDENT return res NEW_LINE DEDENT ancestors [ index ] = root NEW_LINE return min ( findClosestUtil ( root . left , k , ancestors , index + 1 ) , findClosestUtil ( root . right , k , ancestors , index + 1 ) ) NEW_LINE DEDENT def findClosest ( root , k ) : NEW_LINE INDENT ancestors = [ None for i in range ( 100 ) ] NEW_LINE return findClosestUtil ( root , k , ancestors , 0 ) NEW_LINE DEDENT root = Node ( ' A ' ) NEW_LINE root . left = Node ( ' B ' ) NEW_LINE root . right = Node ( ' C ' ) ; NEW_LINE root . right . left = Node ( ' E ' ) ; NEW_LINE root . right . right = Node ( ' F ' ) ; NEW_LINE root . right . left . left = Node ( ' G ' ) ; NEW_LINE root . right . left . left . left = Node ( ' I ' ) ; NEW_LINE root . right . left . left . right = Node ( ' J ' ) ; NEW_LINE root . right . right . right = Node ( ' H ' ) ; NEW_LINE root . right . right . right . left = Node ( ' K ' ) ; NEW_LINE k = ' H ' ; NEW_LINE print " Distance ▁ of ▁ the ▁ closest ▁ key ▁ from ▁ " + k + " ▁ is " , NEW_LINE print findClosest ( root , k ) NEW_LINE k = ' C ' NEW_LINE print " Distance ▁ of ▁ the ▁ closest ▁ key ▁ from ▁ " + k + " ▁ is " , NEW_LINE print findClosest ( root , k ) NEW_LINE k = ' E ' NEW_LINE print " Distance ▁ of ▁ the ▁ closest ▁ key ▁ from ▁ " + k + " ▁ is " , NEW_LINE print findClosest ( root , k ) NEW_LINE k = ' B ' NEW_LINE print " Distance ▁ of ▁ the ▁ closest ▁ key ▁ from ▁ " + k + " ▁ is " , NEW_LINE print findClosest ( root , k ) NEW_LINE