package binarySearchTree;

// Binary Search Tree implementation
class BST {

private BinNode root; // Root of the BST
private int nodecount; // Number of nodes in the BST

// constructor
BST() {
   root = null;
   nodecount = 0;
}

// Reinitialize tree
public void clear() {
   root = null;
   nodecount = 0;
}

// Insert a record into the tree.
// Records can be anything, but they must be Comparable
// e: The record to insert.
public void insert(int e) {
   root = inserthelp(root, e);
   nodecount++;
}

private BinNode inserthelp(BinNode root, int key) {

   if (root == null) {
         return new LeafNode(key);
   }

   if (key < root.getValue()){
         int rep = root.getRepetitions();
         if (root instanceof InternalNode) {
         } else {
            root = new InternalNode(root.getValue(), null, null);
         }
         root.repetitionCounter = rep;
         ((InternalNode) root).setLeft(inserthelp(((InternalNode) root).leftChild(), key));
   } else if (key > root.getValue()){
         int rep = root.getRepetitions();
         if (root instanceof InternalNode) {
         } else {
            root = new InternalNode(root.getValue(), null, null);
         }
         root.repetitionCounter = rep;
         ((InternalNode) root).setRight(inserthelp(((InternalNode) root).rightChild(), key));
   } else {
         root.repetitionCounter++;
   }
   return root;
}

// Remove a record from the tree
// key: The key value of record to remove
// Returns the record removed, null if there is none.
public int remove(int key) {
   int temp = findhelp(root, key); // First find it
   if (temp != 0) {
         root = removehelp(root, key); // Now remove it
         nodecount--;
   }
   return temp;
}

private BinNode removehelp(BinNode root, int key) {

   return null;
}

// Return the record with key value k, null if none exists
// key: The key value to find
public int find(int key) {
   return findhelp(root,
            key);
}

private int findhelp(BinNode root, int key) {
   return key;
}

// Return the number of records in the dictionary
public int size() {
   return nodecount;
}

private String properQuantityNoun( int value ) {
   if (value == 1) {
         return " occurs 1 time.";
   } else {
         return " occurs " + value + " times.";
   }
}

2 Learning Objectives 1. To apply recursion solutions to solve pro...