Question

Lab 9

You will be inserting values into a generic tree, then printing the values inorder, as well as printing the minimum and maximum values in the tree. Given main(), write the methods in the 'BSTree' class specified by the // TODO: sections. There are 5 TODOs in all to complete.

Ex: If the input is

like
ferment
bought
tasty
can
making
apples
super
improving
juice
wine
-1

the output should be:

Enter the words on separate lines to insert into the tree, enter -1 to stop

The Elements Inorder: apples - bought - can - ferment - improving - juice - like - making - super - tasty - wine - 

The minimum element in the tree is apples

The maximum element in the tree is wine

Main.java

import java.util.Scanner;

public class Main {

   public static void main(String[] args) {

       BSTree<String> tree = new BSTree<String>();
      
       Scanner scrn = new Scanner(System.in);
       System.out.println("Enter the words on separate lines to insert into the tree, enter -1 to stop");
      
       String word = scrn.nextLine();
       while(!word.equals("-1")) {
           tree.addElement(word);
           word = scrn.nextLine();
       }
       System.out.println();
      
       tree.printElements();
      
       System.out.println("\nThe minimum element in the tree is " + tree.findMin());
       System.out.println("\nThe maximum element in the tree is " + tree.findMax());

   }

}

BSTreeNode.java

public class BSTreeNode<T> {

   private T element;
   private BSTreeNode<T> left, right;

   public BSTreeNode(T element) {
       this.element = element;
       this.left = null;
       this.right = null;
   }

   public T getElement() {
       return element;
   }

   public void setElement(T element) {
       this.element = element;
   }

   public BSTreeNode<T> getLeft() {
       return left;
   }

   public void setLeft(BSTreeNode<T> left) {
       this.left = left;
   }

   public BSTreeNode<T> getRight() {
       return right;
   }

   public void setRight(BSTreeNode<T> right) {
       this.right = right;
   }
      
}

BSTree.java

public class BSTree<T> {

   private BSTreeNode<T> root = null;

   // TODO: Write an addElement method that inserts generic Nodes into
   // the generic tree. You will need to use a Comparable Object

// TODO: write the method printElements
       // It should check that the tree isn't empty
       // and prints "The Tree is empty" if it is
       // otherwise prints "The Elements Inorder: "
       // and calls the inorder method

// TODO: write the inorder method that traverses
       // the generic tree and prints the data inorder

// TODO: write the findMin method that returns the
       // minimum value element in the tree

// TODO: write the findMin method that returns the
       // maximum value element in the tree

Answer 1

So, here is the solution of the given problem.
I am attaching the well-commented source code along with the Screenshots of the code as well as output.

Source Code:

Main Class is same as question.

compareTo function in BSTreeNode class

 class BSTreeNode<T> {

   private T element;
   private BSTreeNode<T> left, right;

   public BSTreeNode(T element) {
       this.element = element;
       this.left = null;
       this.right = null;
   }

   public T getElement() {
       return element;
   }

   public void setElement(T element) {
       this.element = element;
   }

   public BSTreeNode<T> getLeft() {
       return left;
   }

   public void setLeft(BSTreeNode<T> left) {
       this.left = left;
   }

   public BSTreeNode<T> getRight() {
       return right;
   }

   public void setRight(BSTreeNode<T> right) {
       this.right = right;
   }



   //first convert the element into String then apply compareTo on both Strings
   public int compareTo(BSTreeNode<T> node){
         return String.valueOf(this.getElement()).compareTo( String.valueOf(node.getElement()));
   }
}

BSTree class:

class BSTree<T> {

   private BSTreeNode<T> root = null;

   //addElement function to add element into the BST
   void addElement(T data){ 
        //creating the node to be inserted
       BSTreeNode<T> node = new BSTreeNode(data);
       
       //if root is null that means tree is null so make the node as root
       if(root == null){
           root = node;
           return;
       }
       //else initialize a temp variable with root and ....
       BSTreeNode<T> temp = root;
       
       //while temp is not null
       while(temp != null){

            //if compareTo function return negative number that means node to be inserted is greater than the current node
           if(temp.compareTo(node)<0){
               //if right is null assign the node to its right
                    if(temp.getRight() != null)
                        temp = temp.getRight();
            //else move to the right of current node
                    else{
                        temp.setRight(node);
                        break;
                    }
               
           }
       //if compareTo function return positive number that means node to be inserted is lesser than the current node
            else {
               //if left is null assign the node to its left
             if(temp.getLeft()  != null)
                temp = temp.getLeft();
            //else move to the left of current node
                else{
                    temp.setLeft(node);
                    break;
                }
            }
       }
   }
   

//function to print elements
    void printElements(){

    //if tree is null print statement and return
        if(root == null){
            System.out.println("The Tree is empty");
            return;
        }
//else call inorder 
        inorder(root);
        System.out.println();
    }
    
    
    
    //inorder function
    void inorder(BSTreeNode<T> node){
        if(node == null)
            return;
        inorder(node.getLeft());
        System.out.print(node.getElement() + " - ");
        inorder(node.getRight());
    }


//to find minimum element print the left most node of the tree as we know left most node of BST is always minimum

    T findMin(){
        if(root == null)
            return null;
        BSTreeNode<T> temp = root;
        while(temp != null && temp.getLeft() != null)
            temp = temp.getLeft();
           
    return temp.getElement();
    }
    
    
//to find maximum element print the right most node of the tree as we know right most node of BST is always maximum
           
      T findMax(){
        if(root == null)
            return null;
        BSTreeNode<T> temp = root;
        while(temp != null &&  temp.getRight() != null)
            temp = temp.getRight();
            
    return temp.getElement();
    }
}

Here are the screenshots:

compareTo function:

BSTree class:

Output of the code:

So, this was the solutions of the problem.
I hope I am able to solve your problem, if yes then do give it a like.
It really helps :)