package treeDemo; import java.util.ArrayList; import… Image transcription textPart 1: Counting Nodes (25 points) The public int count () m
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
