Maximum element between two nodes of BST in java

Java program for Maximum element between two nodes of BST. Here more solutions.

// Java program for
// Detect max nodes between given two nodes of a BST

// Binary Search Tree Node
class TreeNode
{
    // Data value 
    public int data;
    // Indicates left and right subtree
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinarySearchTree
{
    public TreeNode root;
    public BinarySearchTree()
    {
        this.root = null;
    }
    // Insert a new node in BST
    public void addNode(int value)
    {
        // Create a dynamic node of binary search tree 
        TreeNode node = new TreeNode(value);
        
            if (this.root == null)
            {
                // When adds a first node in binary tree
                this.root = node;
            }
            else
            {
                TreeNode find = this.root;
                // Add new node to proper position
                while (find != null)
                {
                    if (find.data >= value)
                    {
                        if (find.left == null)
                        {
                            find.left = node;
                            return;
                        }
                        else
                        {
                            // Visit left sub-tree
                            find = find.left;
                        }
                    }
                    else
                    {
                        if (find.right == null)
                        {
                            find.right = node;
                            return;
                        }
                        else
                        {
                            // Visit right sub-tree
                            find = find.right;
                        }
                    }
                }
            }
       
    }
    TreeNode findNode(TreeNode node, int value)
    {
        if (node != null)
        {
            if (node.data > value)
            {
                // Find node in left subtree
                return findNode(node.left, value);
            }
            else if (node.data < value)
            {
                // Find node in right subtree
                return findNode(node.right, value);
            }
            else
            {
                // When node exist
                return node;
            }
        }
        // When node is not exist
        return null;
    }

    // Find LCA of two BST nodes
    TreeNode lca(TreeNode node, int first, int second)
    {
        if (node != null)
        {
            if (node.data > first && node.data > second)
            {
                return lca(node.left, first, second);
            }
            else if (node.data < first && node.data < second)
            {
                return lca(node.right, first, second);
            }
            
            return node;
            
        }
        return null;
    }
    public void findMaxBetween(int first, int second)
    {
        if (this.root != null)
        {
            // First we are check that given node are exist or not in BST
           
            if (findNode(this.root, first) != null && 
                findNode(this.root, second) != null)
            {
                // If given element is exist then get LCA
                TreeNode node = lca(this.root, first, second);

                int find = first;

                if (first < second)
                {
                    find = second;
                }
                int result = find;
                // node is lca of both node (x,y)
                // so we consider path from node of largest of (x,y)
                // And find max node of this path
                while (node != null)
                {
                    if (node.data > result)
                    {
                        result = node.data;
                    }
                    if (node.data > find)
                    {
                        // Visit to left child
                        node = node.left;
                    }
                    else if (node.data < find)
                    {
                        // Visit to right child
                        node = node.right;
                    }
                    else
                    {
                        break;

                    }
                }
                System.out.println("Max Node Between [" + first + "," + 
                    second + "] is " + result );
            }
            else
            {
                System.out.println("Node [" + first + "," + 
                    second + "] are missing");
            }
        }
        else
        {
            System.out.println("\nEmpty BST");
        }
    }
    public static void main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();
        // Binary search tree
        /*
                    10
                   / \
                  /   \ 
                 /     \
                3      19
               / \    /  \
              1   4  14  50
             / \     
           -3   2          
        */
        tree.addNode(10);
        tree.addNode(3);
        tree.addNode(19);
        tree.addNode(1);
        tree.addNode(4);
        tree.addNode(-3);
        tree.addNode(2);
        tree.addNode(14);
        tree.addNode(50);
        // Testing 
        tree.findMaxBetween(2, 14);
        tree.findMaxBetween(-3, 4);
        tree.findMaxBetween(10, 2);
        tree.findMaxBetween(3, 2);
    }
}

Output

Max Node Between [2,14] is 19
Max Node Between [-3,4] is 4
Max Node Between [10,2] is 10
Max Node Between [3,2] is 3