Complete the code by implementing the following /** * A Simple implementation of

Question

Complete the code by implementing the following

/**
* A Simple implementation of a BST
* TODO: Implement
* 1. size method
* 2. min/max method
* 3. height method (both for the tree and any given branch)
* 3. contains/search method that return a reference to the node in the BST (null if not found)
* 4. remove method (if the node to be removed is not the leaf node ==> re-insert its children into the BST
*
*
*
*/

//node class used in BST - could be implemented as a nested class
class Node {
   //constructor
   public Node(int data){
       this.data = data;
   }
  
   //attributes
   public int data;
   public Node left;
   public Node right;
}

/**
* The Actual BST
*
*
*/
public class BST {
public BST(){ //constructor
   this.root = null;
}
  
/**
* Insert interface for user - the data will be inserted starting from the BST root
* @param data
*/
public void insert(int data){
   if(this.root == null){//handle empty tree
       this.root = new Node(data);
   }else { //tree has nodes, then start at the root
    insert(this.root, data);
   }
}
/**
* Helper method that inserts the nodes with BST properties
* @param v - node/root to start with
* @param data - data to be inserted
*/
private void insert(Node v, int data){
   //====handle exception here
   if(v == null)
       return;
   //==============================
  
   if(v.data < data) { //insert to the right branch
       if(v.right != null){
           insert(v.right, data);
       }else{
           v.right = new Node (data);
       }
   }else if (v.data > data){ //insert to the left branch
       if(v.left != null){
           insert(v.left, data);
       }else{
           v.left = new Node(data);
       }
   }
}
  
   //traverse the tree pre-order fashion - this is the interface for the user
   public String preOrder(){
       return doPreOrder(this.root); //start at the root
   }
  
   //this is the actual code handling the pre-order traversal
   private String doPreOrder(Node v){
       if(v != null){
           return v.data + " " +
       doPreOrder(v.left) +
       doPreOrder(v.right);
          
       }else{ //nothing to do ==> extends out of the leaf
           return "";
       }
   }
   //traverse the tree in-order fashion - this is the interface for the user
       public String inOrder(){
           return doInOrder(this.root); //start at the root
       }
      
       //this is the actual code handling the in-order traversal
       private String doInOrder(Node v){
           if(v != null){
           return doInOrder(v.left) +
           v.data + " " +
           doInOrder(v.right);
              
           }else{ //nothing to do ==> extends out of the leaf
               return "";
           }
       }
//attribute
private Node root;
  
  
  
//=========== DRIVER ================
public static void main(String[] args){
   BST t = new BST(); //create a BST
  
   //insert some data into the tree
   t.insert(5);
   t.insert(2);
   t.insert(1);
   t.insert(3);
   t.insert(7);
   //print out the tree
   System.out.println(t.preOrder()); //expected 5 2 1 3 7
   System.out.println(t.inOrder()); //expected 1 2 3 5 7
  
}
}

Explanation / Answer

public int Size() {
       return Size(root);
   }

   private int Size(Node n) {
       if (n != null) {
           int size = 1;
           if (n.left != null) {
               size += Size(n.left);
           }
           if (n.right != null) {
               size += Size(n.right);
           }
           return size;
       } else
           return 0;
   }

   public int min() {
       return min(root).data;
   }
  
   private Node min(Node v) {
       while(v.left != null) {
           v = v.left;
       }
       return v;
   }

   public int max() {
       return max(root).data;
   }

   private Node max(Node v) {
       while(v.right != null) {
           v = v.right;
       }
       return v;
   }

   public int height() {
       return height(root);
   }

   public int height(Node n) {
       if (n == null)
           return 0;
       int height = 1;
       if (n.left != null) {
           height += height(n.left);
       }
       if (n.right != null) {
           height = Math.max(height, 1 + height(n.right));
       }
       return height;
   }

   public Node Search(int n) {
       return Search(root, n);
   }

   private Node Search(Node v, int n) {
       if (v != null) {
           if (v.data == n)
               return v;
           else if (v.data < n)
               return Search(v.right, n);
           else if (v.data > n)
               return Search(v.left, n);
       }
       return null;
   }

   public void remove(int n) {
       remove(root, n);
   }

   private void remove(Node v, int n) {
       if (v == null)
           return;
       if (v.data == n) {
           if (v.left == null || v.right == null) {
               Node current = v.left == null ? v.right : v.left;
               if (getParent(v.data, root).left == v)
                   getParent(v.data, root).left = current;
               else
                   getParent(v.data, root).right = current;
           } else {
               Node successor = max(v.left);
               int data = successor.data;
               remove(v.left, data);
               v.data = data;
           }
       } else if (v.data > n) {
           remove(v.left, n);
       } else {
           remove(v.right, n);
       }
   }

   private Node getParent(int n, Node v) {
       if (v.data < n) {
           if (v.right != null) {
               if (v.right.data == n)
                   return v;
               return getParent(n, v.right);
           }
       }
       if (v.data > n) {
           if (v.left != null) {
               if (v.left.data == n)
                   return v;
               return getParent(n, v.left);
           }
       }
       return null;
   }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.