Question

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

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());

   }

}

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;
   }
      
}

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

Please find the code for the above program below:

BSTree.java Class :

public class BSTree<T> {

private BSTreeNode<T> root = null;

@SuppressWarnings("unchecked")
public void addElement(String word) {
if (root == null) { // must handle case of empty tree first
root = new BSTreeNode<T>((T)word);
return;
}
BSTreeNode<T> loc = root; // start search downward at root
while (true) {
if (word.compareTo(loc.getElement().toString()) < 0) { // look 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 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();
}

}

PS : The code was tested with the test case mentioned in the question. Please run another test case at your end.

Thankyou