Question

In java,

Finding the maximum value in a BST (Binary Search Tree). Students need to write the code.

Answer 1

As we have to find the maximum value in a BST (Binary Search Tree), let us understand the properties of BST,

1. The element which is smaller than the root element will go to the left side of BST.

2. The element which is greater than the root element will go to the rigth side of BST.

Our aim is to find the maximum value in a BST, so no doubt it will be in the most right side of the BST.

We will create 2 classes namely

1. Node class
2. BST_MAX class

Node class contains the basic structure of a node, that is value, leftChild and rightChild.

BST_MAX class contains main method and methods for creating new node, inserting new node.

Let us see and understand the code,

import java.util.Scanner;
//creating structure of a node using class
class Node 
{ 
        int value; 
        Node leftChild; 
        Node rightChild; 
};
 
//class contains main method
class BST_MAX 
{ 
        
        //method for creating new node
        //new node does not have left and right child hence null
        public static Node newNode(int value) 
        { 
            Node node = new Node(); 
            node.value = value; 
            node.leftChild = null; 
            node.rightChild = null; 
            return node; 
        } 
  
        //method to insert new node everytime 
        public static Node insertNode(Node node, int value) 
        { 
                //check if BST is empty (whether it first node of tree)
                if (node == null) 
                {
                    return newNode(value); 
                }
                //not the first node (traverse and feed value in right position)
                else 
                { 
                        //if value is less than or equal to parent node then keep recursion at left side
                        if (value <= node.value) 
                        {
                                node.leftChild = insertNode(node.leftChild, value); 
                        }
                        //if value is greater than parent node then keep recursion with right side 
                        else
                        {
                                node.rightChild = insertNode(node.rightChild, value); 
                        }
                } 
                return node; 
        } 
  
        //method to find max element in BST
        //traversing the tree to the right most side    
        public static int maxElement(Node node) 
        {
                Node temp = node; 
                while (temp.rightChild != null)
                {
                        temp = temp.rightChild; 
                }      
                return temp.value; 
        } 

        //main method (execution starts from here)
        public static void main(String args[])  
        { 
                Node root = null; 
                Scanner sc=new Scanner(System.in);
                System.out.println("Enter total number of elements: ");
                int n=sc.nextInt();
                //if thier is no value
                if(n<=0)
                {
                        System.out.println("Does not have max element");
                } 
                //else values exists in BST
                else
                {
                        System.out.println("Enter values: ");
                        int value=sc.nextInt();
                        root=insertNode(root,value);    //root node
                        while(n>1)
                        {
                                value=sc.nextInt();
                                insertNode(root,value);
                                n--;
                        }
                        int max=maxElement(root);
                        System.out.println("Maximum Value in Binary Search Tree is "+max);
                }       
        } 
} 

The code is successfully compiled and asked the user to enter total number of elements want to enter in BST.

Compile and Run in cmd:

INPUT:

OUTPUT: