Question

Copy the file SimplerBST.java from the week 1 examples package and rename the file and class A3BST. Add two public methods:

• one named countTwins that takes no parameters and that, when called, traverses every node of the tree to count the number of nodes having two children.
• one named lessThanValueCount that takes a paremeter of generic type V, and that, when called, traverses every node of the tree to count the number of nodes whose value (not its key) is less than the value passed as a parameter.

package assignment3;
import algs4.*;

public class A3BST, V> {
  
  
   private Node root; // root of BST

   private static class Node,V> {
       public K key;            // sorted by key
       public V val;        // associated data
       public Node left, right;     // left and right subtrees

       public Node(K key, V val) {
           this.key = key;
           this.val = val;
       }
   }
  
   public A3BST() {}

   /* *********************************************************************
   * Search BST for given key, and return associated value if found,
   * return null if not found
   ***********************************************************************/
   // does there exist a key-value pair with given key?
   public boolean contains(K key) {
       return get(key) != null;
   }

   // return value associated with the given key, or null if no such key exists
   public V get(K key) { return get(root, key); }
   private V get(Node x, K 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.val;
   }

   /* *********************************************************************
   * Insert key-value pair into BST
   * If key already exists, update with new value
   ***********************************************************************/
   public void put(K key, V val) {
       if (val == null) { delete(key); return; }
       root = put(root, key, val);
   }

   private Node put(Node x, K key, V val) {
       if (x == null) return new Node<>(key, val);
       int cmp = key.compareTo(x.key);
       if (cmp < 0)
           x.left = put(x.left, key, val);
       else if (cmp > 0)
           x.right = put(x.right, key, val);
       else
           x.val = val;
       return x;
   }

   /* *********************************************************************
   * Delete
   ***********************************************************************/

   public void delete(K key) {
       root = delete(root, key);
   }
  
   private Node delete(Node x, K key) {
       if (x == null) return null;
       int cmp = key.compareTo(x.key);
       if (cmp < 0) x.left = delete(x.left, key);
       else if (cmp > 0) x.right = delete(x.right, key);
       else {
           // x is the node to be deleted.
           // The value returned in each of these cases below
           // becomes the value of the child reference from
           // the parent of x. Returning a null makes that
           // reference a null and so cuts x off, causing its
           // automatic deletion.
          
           // Determine how many children x has.
           if (x.right == null && x.left == null){
               // This is a leaf node.
               return null;
           } else if (x.right == null) {
               // One child, to the left.
               return x.left;
           } else if (x.left == null) {
               // One child, to the right.
               return x.right;
           } else {
               // Node x has two children.
               // Find the node in x's right subtree with
               // the minimum key.
               Node rightTreeMinNode = findMin(x.right);
               x.key = rightTreeMinNode.key;
               x.val = rightTreeMinNode.val;
               x.right = delete(x.right, rightTreeMinNode.key);
           }
       }
       return x;
   }
  
   private Node findMin(Node x) {
       if (x.left == null) return x;
       else return findMin(x.left);
   }

   public void printKeys() {
       printKeys(root);
   }
  
   private void printKeys(Node x) {
       if (x == null) return;
       printKeys(x.left);
       StdOut.println(x.key);
       printKeys(x.right);
   }
  
   public Iterable keys() {
       Queue q = new Queue<>();
       inOrder(root, q);
       return q;
   }

   private void inOrder(Node x, Queue q) {
       if (x == null) return;
       inOrder(x.left, q);
       q.enqueue(x.key);
       inOrder(x.right, q);
   }
  
   public int height() {
       return height(root);
   }
  
   private int height(Node x) {
       if (x == null) return -1;
       return 1+Math.max(height(x.left), height(x.right));
   }

   /* ***************************************************************************
   * Visualization
   *****************************************************************************/

   public void drawTree() {
       if (root != null) {
           StdDraw.setPenColor (StdDraw.BLACK);
           StdDraw.setCanvasSize(1200,700);
           drawTree(root, .5, 1, .25, 0);
       }
   }
   private void drawTree (Node n, double x, double y, double range, int depth) {
       int CUTOFF = 10;
       StdDraw.text (x, y, n.key.toString ());
       StdDraw.setPenRadius (.007);
       if (n.left != null && depth != CUTOFF) {
           StdDraw.line (x-range, y-.08, x-.01, y-.01);
           drawTree (n.left, x-range, y-.1, range*.5, depth+1);
       }
       if (n.right != null && depth != CUTOFF) {
           StdDraw.line (x+range, y-.08, x+.01, y-.01);
           drawTree (n.right, x+range, y-.1, range*.5, depth+1);
       }
   }
  
   /* ***************************************************************************
   * countTwins method
   *****************************************************************************/
   public int countTwins(Node node) {
      
       //traverse every node of the tree and count
       //nodes having two children
      
       //run time O(n) --- n nodes are visited --- understand the structure of the tree
      
       if(node == null) {
           return 0;
       }
      
       //set the condition if the both left and right are populated
       if (node.left != null && node.right != null) {
           //return the count
           return 1 + countTwins(node.left) + countTwins(node.right);
       }
      
   //else traverse
       return countTwins(node.left) + countTwins(node.right);
      
   }
  
  
  
   /* ***************************************************************************
   * lessThanValueCount method
   *****************************************************************************/
   public int lessThanValueCount(Node x, V key) {
      
       if (x == null) {
   return 0;
   }
          
   if (x.val.equals(key)) {
   return 1 + lessThanValueCount(x.left, key) + lessThanValueCount(x.right, key);
   }
   return lessThanValueCount(x.left, key) + lessThanValueCount(x.right, key);
   }
   }
  

Answer 1

//if you have any query regarding the answer then let me know.

//if you like it, then give a thumbs up.

package assignment3;
import algs4.*;

public class A3BST, V> {
  
  
private Node root; // root of BST

private static class Node,V> {
public K key; // sorted by key
public V val; // associated data
public Node left, right; // left and right subtrees

public Node(K key, V val) {
this.key = key;
this.val = val;
}
}
  
public A3BST() {}

/* *********************************************************************
* Search BST for given key, and return associated value if found,
* return null if not found
***********************************************************************/
// does there exist a key-value pair with given key?
public boolean contains(K key) {
return get(key) != null;
}

// return value associated with the given key, or null if no such key exists
public V get(K key) { return get(root, key); }
private V get(Node x, K 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.val;
}

/* *********************************************************************
* Insert key-value pair into BST
* If key already exists, update with new value
***********************************************************************/
public void put(K key, V val) {
if (val == null) { delete(key); return; }
root = put(root, key, val);
}

private Node put(Node x, K key, V val) {
if (x == null) return new Node<>(key, val);
int cmp = key.compareTo(x.key);
if (cmp < 0)
x.left = put(x.left, key, val);
else if (cmp > 0)
x.right = put(x.right, key, val);
else
x.val = val;
return x;
}

/* *********************************************************************
* Delete
***********************************************************************/

public void delete(K key) {
root = delete(root, key);
}
  
private Node delete(Node x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);
else if (cmp > 0) x.right = delete(x.right, key);
else {
// x is the node to be deleted.
// The value returned in each of these cases below
// becomes the value of the child reference from
// the parent of x. Returning a null makes that
// reference a null and so cuts x off, causing its
// automatic deletion.
  
// Determine how many children x has.
if (x.right == null && x.left == null){
// This is a leaf node.
return null;
} else if (x.right == null) {
// One child, to the left.
return x.left;
} else if (x.left == null) {
// One child, to the right.
return x.right;
} else {
// Node x has two children.
// Find the node in x's right subtree with
// the minimum key.
Node rightTreeMinNode = findMin(x.right);
x.key = rightTreeMinNode.key;
x.val = rightTreeMinNode.val;
x.right = delete(x.right, rightTreeMinNode.key);
}
}
return x;
}
  
private Node findMin(Node x) {
if (x.left == null) return x;
else return findMin(x.left);
}

public void printKeys() {
printKeys(root);
}
  
private void printKeys(Node x) {
if (x == null) return;
printKeys(x.left);
StdOut.println(x.key);
printKeys(x.right);
}
  
public Iterable keys() {
Queue q = new Queue<>();
inOrder(root, q);
return q;
}

private void inOrder(Node x, Queue q) {
if (x == null) return;
inOrder(x.left, q);
q.enqueue(x.key);
inOrder(x.right, q);
}
  
public int height() {
return height(root);
}
  
private int height(Node x) {
if (x == null) return -1;
return 1+Math.max(height(x.left), height(x.right));
}

/* ***************************************************************************
* Visualization
*****************************************************************************/

public void drawTree() {
if (root != null) {
StdDraw.setPenColor (StdDraw.BLACK);
StdDraw.setCanvasSize(1200,700);
drawTree(root, .5, 1, .25, 0);
}
}
private void drawTree (Node n, double x, double y, double range, int depth) {
int CUTOFF = 10;
StdDraw.text (x, y, n.key.toString ());
StdDraw.setPenRadius (.007);
if (n.left != null && depth != CUTOFF) {
StdDraw.line (x-range, y-.08, x-.01, y-.01);
drawTree (n.left, x-range, y-.1, range*.5, depth+1);
}
if (n.right != null && depth != CUTOFF) {
StdDraw.line (x+range, y-.08, x+.01, y-.01);
drawTree (n.right, x+range, y-.1, range*.5, depth+1);
}
}
  
/* ***************************************************************************
* countTwins method
*****************************************************************************/
public int countTwins(Node node) {
  
//traverse every node of the tree and count
//nodes having two children
  
//run time O(n) --- n nodes are visited --- understand the structure of the tree
  
if(node == null) {
return 0;
}
  
//set the condition if the both left and right are populated
if (node.left != null && node.right != null) {
//return the count
return 1 + countTwins(node.left) + countTwins(node.right);
}
  
//else traverse
return countTwins(node.left) + countTwins(node.right);
  
}



//---------------------*****************----------------------------
// CountTwin() with no parameter
//---------------------*****************----------------------------

public int countTwins()
{
   Node node=root;
   int count=0;
     
   //talking queue.
   Queue<Node> q=new LinkedList<Node>;   
   q.add(node);
     
   while(q.isEmpty()!=true)
   {
       Node temp=q.poll();
       if(temp.left!=null && temp.right!=null)
       {
       count++;     
       }
         
       if(temp.left!=null)
       {
           q.add(temp.left);
       }
       if(temp.right!=null)
       {
           q.add(temp.right);
       }
   }
     
   return count;
}

  
/* ***************************************************************************
* lessThanValueCount method
*****************************************************************************/
public int lessThanValueCount(Node x, V key) {
  
if (x == null) {
return 0;
}
  
if (x.val.equals(key)) {
return 1 + lessThanValueCount(x.left, key) + lessThanValueCount(x.right, key);
}
return lessThanValueCount(x.left, key) + lessThanValueCount(x.right, key);
}
}




//---------------------*****************----------------------------
// lessThanValueCount that take V
//---------------------*****************----------------------------

public int lessThanValueCount(V v)
{
  
   Node node=root;
   int count=0;
     
   Queue<Node> q=new LinkedList<Node>;
   q.add(node);
     
   while(q.isEmpty()!=true)
   {
       Node temp=q.poll();
       if(temp.val<v)
       {
           count++;
       }
       if(temp.left!=null)
       {
           q.add(temp.left);
       }
       if(temp.right!=null)
       {
           q.add(temp.right);
       }
   }
     
   return count;
     
}