In Java Binary search trees:

Using the TreeNode1 source code (attached at bottom), build a somewhat balanced BST with 15 nodes. Using the traverse method as a guide, write the following methods:

*postOrderTraversal

*preOrderTraversal

*nodeCount

*leafCount

*remove (code the 3 scenarios: remove node with only left child, remove node with only right child, remove node with two children)

Test all methods on your BST, making sure to test them before and after executing the 3 different removal scenarios. Draw the tree you traverse and draw each change to the tree as you remove nodes according to the 3 scenarios.

/** * Class that represents a binary tree node * * */ public class TreeNode1 { /** the data stored at this node */ private String data; /** the left child */ private TreeNode1 left; /** the right child */ private TreeNode1 right; /** * Constructor that takes the string * to store * @param something the string to store */ public TreeNode1(String something) { data = something; left = null; right = null; } /** * Method to return the data * @return the string data at this node */ public String getData() { return data; } /** * Method to set the data at this node * @param something the data to use */ public void setData(String something){data = something;} /** * Method to get the left child * @return the left child (may be null) */ public TreeNode1 getLeft() {return left;} /** * Method to get the right child * @return the right child (may be null) */ public TreeNode1 getRight() {return right;} /** * Method to set the left child * @param newLeft the new left child */ public void setLeft(TreeNode1 newLeft) {left = newLeft;} /** * Method to set the right child * @param newRight the new right child */ public void setRight(TreeNode1 newRight) {right = newRight;} /** * Method to return a string of information * @return the information string */ public String toString() { return "This: " + this.getData()+ " Left: " + this.getLeft() + " Right: " + this.getRight(); } public void insert(TreeNode1 newOne){ if (this.data.compareTo(newOne.data) > 0){ if (this.getLeft() == null){ this.setLeft(newOne); } else { this.getLeft().insert(newOne); } } else { if (this.getRight() == null){ this.setRight(newOne); } else { this.getRight().insert(newOne); } } } public void addLast(TreeNode1 newOne) { if (this.getRight() == null) { this.setRight(newOne); } else { this.getRight().addLast(newOne); } } public String traverse() { String returnValue = ""; //Visit left if(this.getLeft() != null) { returnValue += " " + this.getLeft().traverse(); } //Visit me returnValue += " " + this.getData(); //Visit right if (this.getRight() != null) { returnValue += " " + this.getRight().traverse(); } return returnValue; } public TreeNode1 find(String someValue) { if (this.getData().compareTo(someValue) == 0) { return this; } if (this.data.compareTo(someValue) > 0) { if (this.getLeft() == null) { return null; } else { return this.getLeft().find(someValue); } } else { if(this.getRight() == null) { return null; } else { return this.getRight().find(someValue); } } } public void addFirst(TreeNode1 newOne) { if (this.getLeft() == null){ this.setLeft(newOne); } else { this.getLeft().addFirst(newOne); } } }