Question

Java Program: 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

//BSTree.java


public class BSTree<T> {

private BSTreeNode<T> root = null;

@SuppressWarnings("unchecked")

//Defining addElement function

public void addElement(String word) {

if (root == null) { // if root is null
root = new BSTreeNode<T>((T)word);
return;

}

BSTreeNode<T> loc = root; // start searching downward at root

while (true) {

if (word.compareTo(loc.getElement().toString()) < 0) { // look towards left
if (loc.getLeft()!= null) loc = loc.getLeft();
else
{
   BSTreeNode<T> leftNode = new BSTreeNode<T>((T) word);
   loc.setLeft(leftNode);
   break;
}
}
else if (word.compareTo(loc.getElement().toString()) > 0) { // look towards right
if (loc.getRight() != null) loc = loc.getRight();
else
{
   BSTreeNode<T> rightNode = new BSTreeNode<T>((T) word);
   loc.setRight(rightNode);
   break;
}
}
else break; // found! Don't insert
}
   }

// 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
public void printElements()
{
   if(root == null)
   {
       System.out.println("The Tree is empty");
   }
   else
   {
       System.out.println("The Elements Inorder: ");
       inorder();
   System.out.println();
   }
         
}
  
// TODO: write the inorder method that traverses
// the generic tree and prints the data inorder
public void inorder()
{
   inorderTraversal(root);
}

// inorderT: recursive function that does the work
private void inorderTraversal(BSTreeNode<T> t) {
if (t != null) {
   inorderTraversal(t.getLeft());
System.out.print(t.getElement() + " ");
inorderTraversal(t.getRight());
}
}

// TODO: write the findMin method that returns the
// minimum value element in the tree
public String findMin()
{
   BSTreeNode<T> currentNode = root;
   while(currentNode.getLeft()!=null)
   {
       currentNode = currentNode.getLeft();
   }
     
   return currentNode.getElement().toString();
}

// TODO: write the findMin method that returns the
// maximum value element in the tree
public String findMax()
{
   BSTreeNode<T> currentNode = root;
   while(currentNode.getRight()!=null)
   {
       currentNode = currentNode.getRight();
   }
     
   return currentNode.getElement().toString();
}

}