Closest leaf to a given node in Binary Tree | Utility class to create a new node ; This function finds closest leaf to root . This distance is stored at * minDist . ; base case ; If this is a leaf node , then check if it is closer than the closest so far ; Recur for left and right subtrees ; This function finds if there is closer leaf to x through parent node . ; Base cases ; Search x in left subtree of root ; If left subtree has x ; Find closest leaf in right subtree ; Search x in right subtree of root ; If right subtree has x ; Find closest leaf in left subtree ; Returns minimum distance of a leaf from given node x ; Initialize result ( minimum distance from a leaf ) ; Find closest leaf down to x ; See if there is a closer leaf through parent ; Driver Code ; Let us create Binary Tree shown in above example
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def findLeafDown ( root , lev , minDist ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( root . left == None and root . right == None ) : NEW_LINE INDENT if ( lev < ( minDist [ 0 ] ) ) : NEW_LINE INDENT minDist [ 0 ] = lev NEW_LINE DEDENT return NEW_LINE DEDENT findLeafDown ( root . left , lev + 1 , minDist ) NEW_LINE findLeafDown ( root . right , lev + 1 , minDist ) NEW_LINE DEDENT def findThroughParent ( root , x , minDist ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if ( root == x ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT l = findThroughParent ( root . left , x , minDist ) NEW_LINE if ( l != - 1 ) : NEW_LINE INDENT findLeafDown ( root . right , l + 2 , minDist ) NEW_LINE return l + 1 NEW_LINE DEDENT r = findThroughParent ( root . right , x , minDist ) NEW_LINE if ( r != - 1 ) : NEW_LINE INDENT findLeafDown ( root . left , r + 2 , minDist ) NEW_LINE return r + 1 NEW_LINE DEDENT return - 1 NEW_LINE DEDENT def minimumDistance ( root , x ) : NEW_LINE INDENT minDist = [ 999999999999 ] NEW_LINE findLeafDown ( x , 0 , minDist ) NEW_LINE findThroughParent ( root , x , minDist ) NEW_LINE return minDist [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 12 ) NEW_LINE root . right = newNode ( 13 ) NEW_LINE root . right . left = newNode ( 14 ) NEW_LINE root . right . right = newNode ( 15 ) NEW_LINE root . right . left . left = newNode ( 21 ) NEW_LINE root . right . left . right = newNode ( 22 ) NEW_LINE root . right . right . left = newNode ( 23 ) NEW_LINE root . right . right . right = newNode ( 24 ) NEW_LINE root . right . left . left . left = newNode ( 1 ) NEW_LINE root . right . left . left . right = newNode ( 2 ) NEW_LINE root . right . left . right . left = newNode ( 3 ) NEW_LINE root . right . left . right . right = newNode ( 4 ) NEW_LINE root . right . right . left . left = newNode ( 5 ) NEW_LINE root . right . right . left . right = newNode ( 6 ) NEW_LINE root . right . right . right . left = newNode ( 7 ) NEW_LINE root . right . right . right . right = newNode ( 8 ) NEW_LINE x = root . right NEW_LINE print ( " The ▁ closest ▁ leaf ▁ to ▁ the ▁ node ▁ with ▁ value " , x . key , " is ▁ at ▁ a ▁ distance ▁ of " , minimumDistance ( root , x ) ) NEW_LINE DEDENT