Find the closest element in Binary Search Tree | Utility that allocates a new node with the given key and NULL left and right pointers . ; Function to find node with minimum absolute difference with given K min_diff -- > minimum difference till now min_diff_key -- > node having minimum absolute difference with K ; If k itself is present ; update min_diff and min_diff_key by checking current node value ; if k is less than ptr -> key then move in left subtree else in right subtree ; Wrapper over maxDiffUtil ( ) ; Initialize minimum difference ; Find value of min_diff_key ( Closest key in tree with k ) ; Driver Code
class newnode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . key = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def maxDiffUtil ( ptr , k , min_diff , min_diff_key ) : NEW_LINE INDENT if ptr == None : NEW_LINE INDENT return NEW_LINE DEDENT if ptr . key == k : NEW_LINE INDENT min_diff_key [ 0 ] = k NEW_LINE return NEW_LINE DEDENT if min_diff > abs ( ptr . key - k ) : NEW_LINE INDENT min_diff = abs ( ptr . key - k ) NEW_LINE min_diff_key [ 0 ] = ptr . key NEW_LINE DEDENT if k < ptr . key : NEW_LINE INDENT maxDiffUtil ( ptr . left , k , min_diff , min_diff_key ) NEW_LINE DEDENT else : NEW_LINE INDENT maxDiffUtil ( ptr . right , k , min_diff , min_diff_key ) NEW_LINE DEDENT DEDENT def maxDiff ( root , k ) : NEW_LINE INDENT min_diff , min_diff_key = 999999999999 , [ - 1 ] NEW_LINE maxDiffUtil ( root , k , min_diff , min_diff_key ) NEW_LINE return min_diff_key [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newnode ( 9 ) NEW_LINE root . left = newnode ( 4 ) NEW_LINE root . right = newnode ( 17 ) NEW_LINE root . left . left = newnode ( 3 ) NEW_LINE root . left . right = newnode ( 6 ) NEW_LINE root . left . right . left = newnode ( 5 ) NEW_LINE root . left . right . right = newnode ( 7 ) NEW_LINE root . right . right = newnode ( 22 ) NEW_LINE root . right . right . left = newnode ( 20 ) NEW_LINE k = 18 NEW_LINE print ( maxDiff ( root , k ) ) NEW_LINE DEDENT