text: Maximum element between two nodes of BST | C ++ program to find maximum element in the path between two Nodes of Binary Search Tree . ; Create and return a pointer of 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { struct Node * left , * right ; int data ; } ; Node * createNode ( int x ) { Node * p = new Node ; p -> data = x ; p -> left = p -> right = NULL ; return p ; } void insertNode ( struct Node * root , int x ) { Node * p = root , * q = NULL ; while ( p != NULL ) { q = p ; if ( p -> data < x ) p = p -> right ; else p = p -> left ; } if ( q == NULL ) p = createNode ( x ) ; else { if ( q -> data < x ) q -> right = createNode ( x ) ; else q -> left = createNode ( x ) ; } } int maxelpath ( Node * q , int x ) { Node * p = q ; int mx = INT_MIN ; while ( p -> data != x ) { if ( p -> data > x ) { mx = max ( mx , p -> data ) ; p = p -> left ; } else { mx = max ( mx , p -> data ) ; p = p -> right ; } } return max ( mx , x ) ; } int maximumElement ( struct Node * root , int x , int y ) { Node * p = root ; while ( ( x < p -> data && y < p -> data ) || ( x > p -> data && y > p -> data ) ) { if ( x < p -> data && y < p -> data ) p = p -> left ; else if ( x > p -> data && y > p -> data ) p = p -> right ; } return max ( maxelpath ( p , x ) , maxelpath ( p , y ) ) ; } int main ( ) { int arr [ ] = { 18 , 36 , 9 , 6 , 12 , 10 , 1 , 8 } ; int a = 1 , b = 10 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; struct Node * root = createNode ( arr [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) insertNode ( root , arr [ i ] ) ; cout << maximumElement ( root , a , b ) << endl ; return 0 ; }