This project is to ask you to write five methods for implementation of a Binary Search tree. Each node has the structure

[answerhappygod]

This project is to ask you to write five methods forimplementation of a Binary Search tree. Each node has the structurewith three references that refer to the element, left child andright child.
1. Add and implement the following methods:
1) public int size (Node currRoot):return the number of nodes rooted at tree with root referred bycurrRoot.
2) public boolean search (Node currRoot, inttargetItem): search if a tragetItem is stored on thebinary search tree rooted at currRoot, return true for yes andfalse for no.
3) public boolean insert (Node currRoot, intnewItem): insert a newItem into the binary searchtree using the insert algorithm provided in class. After theinsertion, you should have a binary search tree. Make sure theinserted newItem is not initially on the tree.
4) public int findMax(Node currRoot):return max element stored on the tree rooted at currRoot.
5) public int findMin(Node currRoot):return min element stored on the tree rooted at currRoot.
You can create a project and copy all java files provided inthis project and paste into the src folder of your createdproject. You are recommended to read the provided code first, tofigure out what is already available.
BinarySearchTree.java:
import java.util.ArrayList;
public class BinarySearchTree { private Node root; public BinarySearchTree() { this.root = null; }
public BinarySearchTree(Node root) { this.root = root; } public boolean isEmpty() { if(root==null) returntrue; else return false; } public Node root() { return this.root; } public Node left(Node n) { return n.getLeft(); } public Node right(Node n) { return n.getRight(); } public int numChildren(Node n) { int count=0; if(n.getLeft()!=null)count++; if(n.getRight()!=null)count++; return count; } public boolean isInternal(Node n) { if(numChildren(n)!=0) returntrue; else return false; } public boolean isExternal(Node n) { if(numChildren(n)==0) returntrue; else return false; } public boolean isRoot(Node n) { if(n==root) returntrue; else return false; } public void set(Node n, Integer newElement){ if(n!=null)n.setElement(newElement); } public void inOrder(Node currRoot) { if(currRoot.getLeft()!=null)inOrder(currRoot.getLeft()); System.out.print(currRoot+"\t"); if(currRoot.getRight()!=null)inOrder(currRoot.getRight()); } /**********************************************************************************************/ //implement size() public int size(Node currRoot) { //if tree is empty, return0--base case //else --recursive //return 1+size(lefttree)+size(right tree) } //Implement search to see if a target value isstored on any node of the tree, return true for yes, otherwise,return no public boolean search(Node currRoot, inttargetItem) { //if currRoot is notnull //ifcurrRoot has the target value, return true --base case //ifcurrRoot has left child, return search(left subtree rooted at leftchild) --recursive //ifcurrRoot has right child, return search(right subtree rooted atright child) --recursive //return false if notfound } //Implement insert() public boolean insert(Node currRoot,int newItem) { // if currRoot is null, pack newItem into a nodeand add as root then return true //if currRoot hold an element greater thannewItem //if the currRoot does nothave a leftChild //pack thenewItem into a node and add it as leftchild, then return true //else recursive call inserton the leftSubtree //if currRoot hold an element less thannewItem //if the currRoot does nothave a rightChild //pack thenewItem into a node and add it as rightChild, then returntrue //else recursive call inserton the rightSubtree //return false if failed to insert at thispoint } //Implement findmax() private Node findmax(Node currRoot) { //if currRoot is null, returnnull //else currRoot does not have arightChild, return currRoot //else recursive findMax onrightSubtree }
//Implement findMin() private Node findMin(Node currRoot) { //if currRoot is null, returnnull //else currRoot does not have aleftChild, return currRoot //else recursive findMin onleftSubtree }}
Node.java:
public class Node { private Integer element; private Node left; private Node right; public Node() { this.element=null; this.left=null; this.right=null; } public Node(Integer element) { this.element = element; this.left=null; this.right=null; }
public Node(Node parent, Integer element,Node left, Node right) { this.element = element; this.left = left; this.right = right; }
public Integer getElement() { return element; }
public void setElement(Integer element){ this.element = element; }
public Node getLeft() { return left; }
public void setLeft(Node left) { this.left = left; }
public Node getRight() { return right; }
public void setRight(Node right) { this.right = right; }
@Override public String toString() { return "Node [" + element +"]"; }
}
testClass.java
import java.util.ArrayList;
public class testClass {
public static void main(String[] args){ BinarySearchTree mytree = newBinarySearchTree(); mytree.insert(mytree.root(),45); mytree.insert(mytree.root(),38); mytree.insert(mytree.root(),68); mytree.insert(mytree.root(),20); mytree.insert(mytree.root(),40); mytree.insert(mytree.root(),93); mytree.insert(mytree.root(),85); mytree.insert(mytree.root(),56); System.out.println("In ordertraversal:"); mytree.inOrder(mytree.root());
System.out.println("\nThereare "+mytree.size(mytree.root())+" nodes on the tree."); if(mytree.search(mytree.root(), 56)) System.out.println("Search for 56 on the tree, the answer istrue"); else System.out.println("Search for 56 on the tree, the answer isfalse"); System.out.println("Nodestores maximum is "+mytree.findMax(mytree.root())); System.out.println("Node stores minimum is"+mytree.findMin(mytree.root())); }
}