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
public class Solution { public class Node { public Node left , right ; public int data ; } public static Node createNode ( int x ) { Node p = new Node ( ) ; p . data = x ; p . left = p . right = null ; return p ; } public static void insertNode ( 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 ) ; } } } public static int maxelpath ( Node q , int x ) { Node p = q ; int mx = - 1 ; while ( p . data != x ) { if ( p . data > x ) { mx = Math . Max ( mx , p . data ) ; p = p . left ; } else { mx = Math . Max ( mx , p . data ) ; p = p . right ; } } return Math . Max ( mx , x ) ; } public static int maximumElement ( 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 Math . Max ( maxelpath ( p , x ) , maxelpath ( p , y ) ) ; } public static void Main ( string [ ] args ) { int [ ] arr = new int [ ] { 18 , 36 , 9 , 6 , 12 , 10 , 1 , 8 } ; int a = 1 , b = 10 ; int n = arr . Length ; Node root = createNode ( arr [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { insertNode ( root , arr [ i ] ) ; } Console . WriteLine ( maximumElement ( root , a , b ) ) ; } }