Question

12.9 Lab 9: BST Insert & Delete

visibility_on

This lab will be available until July 7th, 11:59 PM

We have discussed binary search trees, where the nodes in a tree are stored such that an inorder traversal of the tree will produce a list of the data in ascending order. In this lab, you must create a descending order version of the BST, where the largest value is stored as the leftmost node, and the smallest value is stored as the rightmost node.

Complete the binary search tree class, named BST and stored in the file named BST.java. The following methods are required for your code to work with the grading tests.

• a constructor to create an empty tree (This is provided in the template.)
• public void insert(int key) : the key should be inserted (in a new Node) in the tree, such that the tree is in descending order.
• public void delete(int key) : the given key should be removed from the tree.
• public String inorderTraversal() : Perform an inorder traversal of the tree, constructing a String that contains the items in the tree, in the order visited, with a space between each item.

Note 1: This week, the grading tests will call the BST methods, and examine the Strings returned by the traversal method. The traversal method should be very similar to the one you wrote last week. The format of the Strings must match the expected format.

Note 2: You do not need to write a main method

class BST{

private class Node {
public int item;
public Node left;
public Node right;
public Node (int i) { //makes a leaf
item = i;
left = right = null;
}

//***insert Node methods here***

}//end class Node

private Node root;

public BST(){
root = null;
}

   public String inorderTraversal() {

   }//end inorderTraversal

public void insert( int key ){

}//end insert

public void delete( int key ){

}//end delete

//***insert tree methods here***

}//end class BST

Answer 1

//C++ program

class BST{

private class Node {
   public int item;
   public Node left;
   public Node right;
   public Node (int i) { //makes a leaf
       item = i;
       left = right = null;
   }

//***insert Node methods here***

}//end class Node

private Node root;

   public BST(){
       root = null;
   }

   public String inorderTraversal() {
       StringBuilder str = new StringBuilder ();
        inorderTraversal(root , str);
        return str.toString();
   }//end inorderTraversal

private void inorderTraversal(Node root, StringBuilder str) {
   if(root == null) {
       str.append("");
       return;
   }
   inorderTraversal(root.left , str);
   str.append(root.item + " ");
   inorderTraversal(root.right , str);
}

private Node insert(Node root,int data) {
   if(root==null)return new Node(data);
   if(root.item < data)
       root.left = insert(root.left,data);
  
   if(root.item > data)
       root.right=insert(root.right,data);
   return root;
}
public void insert( int key ){
   root = insert(root , key);
}
public Node delete(Node root,int key) {  
   if(root==null)return null;
   else if(root.item > key)
       root.right = delete (root.right,key);
   else if(root.item < key)
       root.left=delete(root.left,key);
   else {
       if(root.left==null)
           return root.right;
       if(root.right==null)
           return root.left;
      
       Node min=findmin(root.left);
       root.item=min.item;
       root.left = delete(root.left,min.item);
      
   }
   return root;
  
}
private Node findmin(Node root) {
   while(root.right!=null)
       root=root.right;
   return root;
}

public void delete( int key ){
   root = delete(root , key);
}
public static void main(String args[]) {
   BST bst = new BST();
   bst.insert(90);
   bst.insert(50);
   bst.insert(40);
   bst.insert(20);
   bst.insert(70);
   bst.insert(30);
   System.out.println(bst.inorderTraversal());
   bst.delete(50);
   System.out.println(bst.inorderTraversal());
   bst.delete(40);
   System.out.println(bst.inorderTraversal());
}
}//end class BST