Shortest distance between two nodes in BST | Python3 program to find distance between two nodes in BST ; Standard BST insert function ; This function returns distance of x from root . This function assumes that x exists in BST and BST is not NULL . ; Returns minimum distance beween a and b . This function assumes that a and b exist in BST . ; Both keys lie in left ; Both keys lie in right same path ; Lie in opposite directions ( Root is LCA of two nodes ) ; This function make sure that a is smaller than b before making a call to findDistWrapper ( ) ; 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 insert ( root , key ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT root = newNode ( key ) NEW_LINE DEDENT elif root . key > key : NEW_LINE INDENT root . left = insert ( root . left , key ) NEW_LINE DEDENT elif root . key < key : NEW_LINE INDENT root . right = insert ( root . right , key ) NEW_LINE DEDENT return root NEW_LINE DEDENT def distanceFromRoot ( root , x ) : NEW_LINE INDENT if root . key == x : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif root . key > x : NEW_LINE INDENT return 1 + distanceFromRoot ( root . left , x ) NEW_LINE DEDENT return 1 + distanceFromRoot ( root . right , x ) NEW_LINE DEDENT def distanceBetween2 ( root , a , b ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return 0 NEW_LINE DEDENT if root . key > a and root . key > b : NEW_LINE INDENT return distanceBetween2 ( root . left , a , b ) NEW_LINE DEDENT if root . key < a and root . key < b : NEW_LINE INDENT return distanceBetween2 ( root . right , a , b ) NEW_LINE DEDENT if root . key >= a and root . key <= b : NEW_LINE INDENT return ( distanceFromRoot ( root , a ) + distanceFromRoot ( root , b ) ) NEW_LINE DEDENT DEDENT def findDistWrapper ( root , a , b ) : NEW_LINE INDENT if a > b : NEW_LINE INDENT a , b = b , a NEW_LINE DEDENT return distanceBetween2 ( root , a , b ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = insert ( root , 20 ) NEW_LINE insert ( root , 10 ) NEW_LINE insert ( root , 5 ) NEW_LINE insert ( root , 15 ) NEW_LINE insert ( root , 30 ) NEW_LINE insert ( root , 25 ) NEW_LINE insert ( root , 35 ) NEW_LINE a , b = 5 , 55 NEW_LINE print ( findDistWrapper ( root , 5 , 35 ) ) NEW_LINE DEDENT