package treeDemo; import java.util.ArrayList; import… Image transcription textPart 1: Counting Nodes (25 points) The public int count () method returns the number ofnodes in the tree. V: .implement this method recursively or iteratively using a stack. ‘ .? ,4 . implement the method recursively; . 1’ 7 ‘need to r “L ” a private helper method. DO NOT CHANGE THE METHOD SIGNATURE … Show more… Show morepackage treeDemo;import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;public class BSTInt {   private static class BSTNode {      private int data;      private BSTNode leftChild;      private BSTNode rightChild;      public BSTNode(int data) {         this.data = data;         leftChild = rightChild = null;      }            public String toString() {         return Integer.toString(data);      }     }      private BSTNode root;      public boolean contains(int d) {      return find(d)!=null;   }      private BSTNode find(int d) {      return recursiveFind(root,d);   }      private BSTNode recursiveFind(BSTNode node, int d) {      //base case, made it to the end or I found it      if(node == null || d == node.data) {         return node;      }      if(d < node.data) {         return recursiveFind(node.leftChild,d);      }      else {         return recursiveFind(node.rightChild,d);      }         }   public void insert(int d) {      BSTNode toInsert = new BSTNode(d);      if(root == null)          root = toInsert;         else          recursiveInsert(root,toInsert);    }      private void recursiveInsert(BSTNode current, BSTNode toInsert) {      if(toInsert.data < current.data) {         if(current.leftChild == null)             current.leftChild = toInsert;         else             recursiveInsert(current.leftChild,toInsert);      }      else if(toInsert.data > current.data){         if(current.rightChild==null)             current.rightChild = toInsert;         else             recursiveInsert(current.rightChild,toInsert);      }   }      //method to iteratively add a node containing data d to the BST   public void iterativeInsert(int d) {      BSTNode toInsert = new BSTNode(d);      if(root == null) {         root = toInsert;         return;      }      BSTNode current = root;      while(current!=null) {         if(d < current.data) {            if(current.leftChild == null) {               current.leftChild = toInsert;               return;            }            else                current = current.leftChild;            }         else if(d>current.data) {            if(current.rightChild == null) {               current.rightChild = toInsert;               return;            }            else                current = current.rightChild;         }      }   }   public void delete(int data) {      recursiveDelete(root,data);   }            private BSTNode recursiveDelete(BSTNode current,int data) {      if(current == null) {         return current;      }      if(current.data == data) {         if(current.leftChild==null && current.rightChild == null) {            return null;         }         else if(current.leftChild == null) {            return current.rightChild;         }         else if(current.rightChild == null) {            return current.leftChild;         }         else {//Still need to handle the case with two children            //This method using the max predecessor strategy            BSTNode predecessor = getMax(current.leftChild);            int d = predecessor.data;            current.data = d;//update data at node            //remove predecessor node            current.leftChild = recursiveDelete(current.leftChild,d);         }      }      else if (data < current.data) {         current.leftChild = recursiveDelete(current.leftChild,data);      }      else {         current.rightChild = recursiveDelete(current.rightChild,data);               }      return current;   }   //assumes node is not null   //used in deleting a node from the see with two children   private BSTNode getMax(BSTNode node){      while(node.rightChild!= null) {         node = node.rightChild;      }      return node;   }      //equals method to compare if two BSTInts are equal   //Computes a Preorder traversal of tree   //and confirms that the structure is the same along    //with the values in the nodes   public boolean equals(Object o) {      BSTInt that = (BSTInt)(o);      if(that.root == null && that.root == null) {         return true;      }      else if(that.root == null || this.root == null) {         return false;      }      Stack preOrderThis = new Stack<>();      Stack preOrderThat = new Stack<>();      preOrderThis.push(root);      preOrderThat.push(that.root);      while(!preOrderThis.isEmpty() && !preOrderThat.isEmpty()) {         BSTNode thisNode = preOrderThis.pop();         BSTNode thatNode = preOrderThat.pop();         if(thisNode.data != thatNode.data){            return false;         }         else {            if(thisNode.leftChild!=null)               preOrderThis.push(thisNode.leftChild);            if(thisNode.rightChild!=null)               preOrderThis.push(thisNode.rightChild);            if(thatNode.leftChild!=null)               preOrderThat.push(thatNode.leftChild);            if(thatNode.rightChild!=null)               preOrderThat.push(thatNode.rightChild);         }      }      return preOrderThis.isEmpty() && preOrderThat.isEmpty();   }      //sum all the nodes in a tree   public int sum() {      return sumRec(root);   }      private int sumRec(BSTNode current) {      if(current == null) {         return 0;      }      else {         return current.data +                sumRec(current.leftChild)+               sumRec(current.rightChild);      }   }      //computed using the sum.   //not the smartest hashCode method   public int hashCode() {      return sum();   }      //to String method so that the tree can be    //printed in a readable format   public String toString() {      return recursiveToString(root,””);       }        //helper method so the tree can be printed   //in a readable format   private String recursiveToString(BSTNode node, String indent) {            if(node == null) {return “”;}      else {         return                recursiveToString(node.rightChild,indent + ”    “)+                “n” + indent  +node.data +               recursiveToString(node.leftChild,indent + ”    “);      }     }      /*     * This is where your implementation starts    */       //Feel free to adda private recursive helper method   public int count() {      return -1;   }       public ArrayList levelOrder(){        ArrayList travOrder = new ArrayList<>();        if(root!=null) {            Queue queue = new LinkedList<>();            queue.add(root);            //and… you will need a while loop        }        return travOrder;    }      //This method should iteratively delete the node containing d from the tree   public void iterativeDelete(int d) {        //feel free to change these variables        //they are just a hint to how you can think about this problem iteratively      BSTNode current = root;      BSTNode parent = null;         }   public static void main(String[] args) {      //You can use this method for basic testing      //But I recommend writing any code you test here as a JUnit test               }}  Computer Science Engineering & Technology Java Programming CS 46B Share QuestionEmailCopy link