Maximum element between two nodes of BST | Python 3 program to find maximum element in the path between two Nodes of Binary Search Tree . Create and return a pointer of new Node . ; Constructor to create a new node ; Insert a new Node in Binary Search Tree . ; Return the maximum element between a Node and its given ancestor . ; Traversing the path between ansector and Node and finding maximum element . ; Return maximum element in the path between two given Node of BST . ; Finding the LCA of Node x and Node y ; Checking if both the Node lie on the left side of the parent p . ; Checking if both the Node lie on the right side of the parent p . ; Return the maximum of maximum elements occur in path from ancestor to both Node . ; Driver Code ; Creating the root of Binary Search Tree ; Inserting Nodes in Binary Search Tree
class createNode : 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 insertNode ( root , x ) : NEW_LINE INDENT p , q = root , None NEW_LINE while p != None : NEW_LINE INDENT q = p NEW_LINE if p . data < x : NEW_LINE INDENT p = p . right NEW_LINE DEDENT else : NEW_LINE INDENT p = p . left NEW_LINE DEDENT DEDENT if q == None : NEW_LINE INDENT p = createNode ( x ) NEW_LINE DEDENT else : NEW_LINE INDENT if q . data < x : NEW_LINE INDENT q . right = createNode ( x ) NEW_LINE DEDENT else : NEW_LINE INDENT q . left = createNode ( x ) NEW_LINE DEDENT DEDENT DEDENT def maxelpath ( q , x ) : NEW_LINE INDENT p = q NEW_LINE mx = - 999999999999 NEW_LINE while p . data != x : NEW_LINE INDENT if p . data > x : NEW_LINE INDENT mx = max ( mx , p . data ) NEW_LINE p = p . left NEW_LINE DEDENT else : NEW_LINE INDENT mx = max ( mx , p . data ) NEW_LINE p = p . right NEW_LINE DEDENT DEDENT return max ( mx , x ) NEW_LINE DEDENT def maximumElement ( root , x , y ) : NEW_LINE INDENT p = root NEW_LINE while ( ( x < p . data and y < p . data ) or ( x > p . data and y > p . data ) ) : NEW_LINE INDENT if x < p . data and y < p . data : NEW_LINE INDENT p = p . left NEW_LINE DEDENT elif x > p . data and y > p . data : NEW_LINE INDENT p = p . right NEW_LINE DEDENT DEDENT return max ( maxelpath ( p , x ) , maxelpath ( p , y ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 18 , 36 , 9 , 6 , 12 , 10 , 1 , 8 ] NEW_LINE a , b = 1 , 10 NEW_LINE n = len ( arr ) NEW_LINE root = createNode ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT insertNode ( root , arr [ i ] ) NEW_LINE DEDENT print ( maximumElement ( root , a , b ) ) NEW_LINE DEDENT