Question

In this assignment, you will add several methods to the Binary Search Tree. You should have completed the following three methods in the lab:

• public void insert(Key key, Value value)
• public Value get(Key key)
• public void inorder(Node root)

For this assignment, you will implement the following:

• public void remove(Node root, Key key)
• public Key getMin(Node n)
• public Key getMax(Node n)
• public int height(Node n)

The main method contains the statements to check whether your implementation works. You need to change anything in the main method.

code provided

import java.util.Scanner;

public class BST<Key extends Comparable<Key>, Value> {

   private Node root; // root of binary search tree

   private class Node {
       private Key key; // sorted by key
       private Value value; // data stored in the node
       private Node left, right; // pointers to left and right subtrees
       private int size; // number of nodes in subtree

       public Node(Key k, Value v) {
           this.key = k;
           this.value = v;          
       }
      
       public Node(Key k, Value v, int size){
           this.key = k;
           this.value = v;
           this.size = size;
       }
   }

   // initialize an empty BST
   public BST() {

   }

   // returns true if tree is empty
   public boolean isEmpty() {
       return size() == 0;
   }

   // returns the number of key-value pairs in the tree
   public int size() {
       return size(root);
   }

   // return the number of key-value pairs in BST rooted at x
   public int size(Node n) {
       // Implement this method
   }

   // Insert key-value pairs in BST, if a key already exists update the value
   public void insert(Key key, Value value){
   // Use your implementation from the lab here
   }
  
   // Search BST for a given key
   public Value get(Key key) {
// Use your implementation from the lab here
   }
  
   // Prints the tree nodes using inorder traversal
   public void inorder(Node root){
       // Use your implementation from the lab here
   }
  
   // remove the node with the given key
   public void remove(Node root, Key key){
       // Implement this method
   }
  

// Returns the minimum key in the tree
   public Key getMin(Node n){
       // Implement this method
   }
  
   // Returns the maximum key in the tree
   public Key getMax(Node n){
// Implement this method
   }
  
   // Returns the height of the tree
   public int height(Node n){
       // Implement this method
   }
  
   public static void main(String[] args){
       Scanner input = new Scanner(System.in);
       BST<Integer, String> bst = new BST<Integer, String>();      
       System.out.println("Enter key value pairs for the BST (-1 to end):");
       while(input.hasNext()){
           int key = input.nextInt();
           if(key == -1) break;              

           String value = input.next();
           bst.insert(key, value);
       }
      
       System.out.println("The size of the BST is:" + bst.size());
       System.out.println("The height of the tree is:" + bst.height(bst.root));
       System.out.println("The node with the minimum key is:" + bst.getMin(bst.root));
       System.out.println("The value stored at the minimum key is: " + bst.get(bst.getMin(bst.root)));
       System.out.println("The node with the maximum key is:" + bst.getMax(bst.root));
       System.out.println("Removing the maximum key: ");
       bst.remove(bst.root, bst.getMax(bst.root));
       System.out.println("The height of the tree is:" + bst.height(bst.root));
       System.out.println("Printing the tree nodes using inorder traversal");
       bst.inorder(bst.root);
       System.out.println("The size of the BST after removal is:" + bst.size());
       System.out.println("Removing the root node: ");
       bst.remove(bst.root, bst.root.key);
       System.out.println("The size of the BST after removal is:" + bst.size());
       System.out.println("The height of the tree after removing the root is:" + bst.height(bst.root));
       bst.inorder(bst.root);
       System.out.println("Removing the right child of the root node: ");
       bst.remove(bst.root, bst.root.right.key);
       bst.inorder(bst.root);
       System.out.println("Size of the BST after removal is:" + bst.size());
   }
}

Answer 1

import java.util.NoSuchElementException;
import java.util.Scanner;

public class BST<Key extends Comparable<Key>, Value> {

private Node root; // root of binary search tree

private class Node {
private Key key; // sorted by key
private Value value; // data stored in the node
private Node left, right; // pointers to left and right subtrees
private int size; // number of nodes in subtree

public Node(Key k, Value v) {
this.key = k;
this.value = v;
}
  
public Node(Key k, Value v, int size){
this.key = k;
this.value = v;
this.size = size;
}
}

// initialize an empty BST
public BST() {

}

// returns true if tree is empty
public boolean isEmpty() {
return size() == 0;
}

// returns the number of key-value pairs in the tree
public int size() {
return size(root);
}

// return the number of key-value pairs in BST rooted at x
public int size(Node n) {
if(n == null) return 0;
else return n.size;
}

// Insert key-value pairs in BST, if a key already exists update the value
public void insert(Key key, Value value){
if (key == null) throw new IllegalArgumentException("calls put() with a null key");
if (value == null) {
remove(root,key);
return;
}
root = insert(root, key, value);
  
}
private Node insert(Node x, Key key, Value val) {
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = insert(x.left, key, val);
else if (cmp > 0) x.right = insert(x.right, key, val);
else x.value = val;
x.size = 1 + size(x.left) + size(x.right);
return x;
}
  
// Search BST for a given key
public Value get(Key key) {
return get(root,key);
}
private Value get(Node x, Key key) {
if (key == null) throw new IllegalArgumentException("calls get() with a null key");
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x.value;
}

// Prints the tree nodes using inorder traversal
public void inorder(Node root){
if(root==null) return;
inorder(root.left);
System.out.println(root.value + " ");
inorder(root.right);
}
  
// remove the node with the given key
public void remove(Node root, Key key){
if (key == null) throw new IllegalArgumentException("calls delete() with a null key");
root = delete(root,key);
}
private Node delete(Node n,Key key){
if(n == null) return null;
int comp = key.compareTo(n.key);
if(comp < 0) n.left = delete(n.left, key);
else if(comp > 0) n.right = delete(n.right, key);
else{
if(n.right == null) return n.left;
if(n.left == null) return n.right;
Node t = n;
n.right = deleteMin(t.right);
n.left = t.left;
}
n.size = size(n.left) + size(n.right) + 1;
return n;
}
public void deleteMin() {
if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
root = deleteMin(root);
  
}

private Node deleteMin(Node x) {
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.size = size(x.left) + size(x.right) + 1;
return x;
}

// Returns the minimum key in the tree
public Key getMin(Node n){
if(isEmpty()) System.out.println("Empty tree");
return min(root).key;

}
  
public Node min(Node n){
if(n.left == null) return n;
else return min(n.left);
}
// Returns the maximum key in the tree
public Key getMax(Node n){
if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
return max(root).key;
}
private Node max(Node x) {
if (x.right == null) return x;
else return max(x.right);
}
// Returns the height of the tree
public int height(Node n){
if(n == null) return -1;
return 1 + Math.max(height(n.left), height(n.right));
}
  
public static void main(String[] args){
Scanner input = new Scanner(System.in);
BST<Integer, String> bst = new BST<Integer, String>();
System.out.println("Enter key value pairs for the BST (-1 to end):");
while(input.hasNext()){
int key = input.nextInt();
if(key == -1) break;

String value = input.next();
bst.insert(key, value);
}
  
System.out.println("The size of the BST is:" + bst.size());
System.out.println("The height of the tree is:" + bst.height(bst.root));
System.out.println("The node with the minimum key is:" + bst.getMin(bst.root));
System.out.println("The value stored at the minimum key is: " + bst.get(bst.getMin(bst.root)));
System.out.println("The node with the maximum key is:" + bst.getMax(bst.root));
System.out.println("Removing the maximum key: ");
bst.remove(bst.root, bst.getMax(bst.root));
System.out.println("The height of the tree is:" + bst.height(bst.root));
System.out.println("Printing the tree nodes using inorder traversal");
bst.inorder(bst.root);
System.out.println("The size of the BST after removal is:" + bst.size());
System.out.println("Removing the root node: ");
bst.remove(bst.root, bst.root.key);
System.out.println("The size of the BST after removal is:" + bst.size());
System.out.println("The height of the tree after removing the root is:" + bst.height(bst.root));
bst.inorder(bst.root);
System.out.println("Removing the right child of the root node: ");
bst.remove(bst.root, bst.root.right.key);
bst.inorder(bst.root);
System.out.println("Size of the BST after removal is:" + bst.size());
}
}

------------------OUTPUT SCREEN------------------

Enter key value pairs for the BST (1 to end): The size of the BST is 3 The height of the tree is:2 The node with the minimum key is:1 The value stored at the minimum key is: 4 The node with the maximum key is:3 Removing The height of the tree is:l Printing the tree nodes using inorder traversal the maximum key: The size of the BST after reoval is 2 Removing the root node: The size of the BST after reoval is 2 The height of the tree after removing the root is:l Removing the right child of the root node Size of the BST after removal is:1

/* PLEASE UPVOTE (THANK YOU IN ADVANCE ) IF YOU SATISFY WITH THE ANSWER. IF ANY QUERY ASK ME IN COMMENT SECTION I WILL RE-SOLVE THE QUESTION FOR YOU */