Need to successfully add the following methods to a JAVA binary tree. The code for the tree is given in the book. THe BinaryTreeTester main class cannot be modified. The methods below will go under the Binary Tree class. I am having trouble integrating the methods successfully to the existing binary tree. So A working solution with the 6 methods will get extra points.

boolean update (int oldValue, int newValue)

-Searches for oldValue in the tree. If found, the data for that node is changed to newValue and the tree is modified such that the node with the new value is placed in the appropriate place in the tree and returns true

-If the oldValue is not found in the tree, the function returns false and the tree stays as is

int findMin()

-If the tree is empty, return -1

-Otherwise, return the smallest value node in the tree

int findMax()

-If the tree is empty, return -1

-Otherwise, return the largest value node in the tree

double calculateAverage()

-If the tree is empty, return 0.0

-Otherwise, return the average value of the tree by adding all node values and dividing by the number of nodes in the tree

int getNumberOfNodes()

-Returns the number of nodes in the tree

boolean isBalanced()

-If the tree is empty, return false

-Otherwise, return true if the tree is balanced

-A balanced is tree is defined as follows:

here is the code: BinaryTree class:

package binarytreetester;

import java.util.Stack;

public class BinaryTree { // insert function private Node root; public BinaryTree() { root = null; } public void insert(int n) { Node current = root; Node newNode = new Node();

newNode.data = n; newNode.left = null; newNode.right = null;

if (root == null) root = newNode; else while(true) if (newNode.data > current.data) if (current.right == null) { current.right = newNode; break; } else current = current.right; else if (current.left == null) { current.left = newNode; break; } else current = current.left; }

// Search function

public Node search(int n) { Node current = root; // assign node to root while (current != null) if (current.data == n) return current; else if (current.data > n) //greater than n we go to the left current = current.left; else current = current.right; return null; } // Delete Function below public boolean remove(int n) { // Check empty tree if (root == null) return false;

// Prepare search for node Node current = root; Node parent = root; boolean currentIsLeft = true; // At this point, current is the node to delete // Now, we check for the situations

// Situation 1 - leaf node if (current.left == null && current.right == null)

// Check if current node is root if (parent == current) root = null;

// Check which child pointer of parent to set else if (currentIsLeft) parent.left = null; else parent.right = null; // Situation 2 - one child. Parent inherits child // or if current is root, root takes child else if (current.left == null) if (parent == current) root = current.right; else if (currentIsLeft) parent.left = current.right; else parent.right = current.right; else if (current.right == null) if (parent == current) root = current.left; else if (currentIsLeft) parent.left = current.left; else parent.right = current.left; // Situation 3: two children else { Node successor = getSuccessor(current);

// Replace current node with successor if (parent == current) root = successor; else if (currentIsLeft) parent.left = successor; else parent.right = successor;

// Successor will always come from the right, so // it must also take deleted nodes left child successor.left = current.left; } return true; } private Node getSuccessor(Node removedNode) { // Prepare successor search by keeping track // of parent and current Node successorParent = removedNode; Node successor = removedNode; Node current = successor.right; // Starting at the right child of the node to be // removed, go down the subtrees left children // until there are no more children on the left while (current != null) { successorParent = successor; successor = current; current = current.left; } // if the successor is somewhere down the subtree, // the parents left child must take the // the successors right child. Then, the // successors right child takes the node // to deletes right child (because successor will // be replacing it. if (successor != removedNode.right) { successorParent.left = successor.right; successor.right = removedNode.right; }

// Note that if the successor is the immediate // right child of the node to delete, we just // return that node (it has no left children and what // ever is on successors right stays that way even // after successor replaces the removed node. return successor; } // Traversing a Tree public void display() { inOrder(root); /* Stack globalStack = new Stack (); globalStack.push(root); int nBlanks = 32; boolean isRowEmpty = false; System.out.println( "......................"); while (isRowEmpty == false) { Stack localStack = new Stack(); isRowEmpty = true; for ( int i = 0; i

void preOrder(Node current) { if (current != null) { System.out.println(current.data); /*display*/preOrder(current.left); /*display*/preOrder(current.right); } } void inOrder(Node current) { if (current != null) { /*display*/inOrder(current.left); System.out.println(current.data); /*display*/inOrder(current.right); } } //PreOrder traversal

// Displaying the tree after it has been organized void postOrder(Node current) { if (current != null) { /*display*/postOrder(current.left); /*display*/postOrder(current.right); System.out.println(current.data); } }

// Update the node /*private boolean update (NOT DONE YET)

// Finding the minimum int findMin(Node node) { Node current = node; if( node == null ){ return -1; } while (current.left != null) { current = current.left; } return (current.data); } // returning the Maximum int findMax (Node node) { Node current = node; if( node == null ){ return -1; } while (current.right != null) { current = current.right; } return (current.data); } // getting the Averagen(NOT DONE YET) // getting the number on nodes static int getNumberOfNodes(Node node) { // empty trees have zero nodes if( node == null ){ return 0; } // all other nodes count the nodes from their left and right subtree // as well as themselves return getNumberOfNodes( node.left ) + getNumberOfNodes( node.right ) + 1; } // Checking to see if the tree is balanced public boolean isBalanced(Node node) { if (node == null) return true;

if (getHeight(node) == -1) return false;

return true; } public int getHeight(Node node) { if (node == null) return 0;

int left = getHeight(node.left); int right = getHeight(node.right);

if (left == -1 || right == -1) return -1;

if (Math.abs(left - right) > 1) { return -1; }

return Math.max(left, right) + 1;

}

CANT modify the BinaryTreeTester Class (LEave as is):

package binarytreetester;

/** * Do not modify anything inside this class. */ public class BinaryTreeTester { public static void main(String[] args) { BinaryTree t1 = new BinaryTree();

// Test insert functions t1.insert(100); t1.insert(50); t1.insert(175); t1.insert(200); t1.insert(150);

// Test displayInOrder and displayPreOrder System.out.println("InOrder: "); t1.inOrder(); System.out.println("PreOrder: "); t1.preOrder();

// Test search function Node searchNode = t1.search(150); if (searchNode != null) System.out.println("150 Found"); else System.out.println("150 Not Found");

searchNode = t1.search(10); if (searchNode != null) System.out.println("10 Found"); else System.out.println("10 Not Found");

// Test delete function System.out.println(); t1.insert(160); t1.insert(170); t1.insert(155); t1.insert(158); t1.preOrder();

// Leaf remove test if (t1.remove(200) == true) System.out.println("200 was found and removed"); else System.out.println("200 was not found"); t1.preOrder();

// Not found remove test if (t1.remove(1) == true) System.out.println("1 was found and removed"); else System.out.println("1 was not found");

// One child remove test if (t1.remove(155) == true) System.out.println("155 was found and removed"); else System.out.println("155 was not found"); t1.preOrder();

// Two children at root remove test if (t1.remove(100) == true) System.out.println("100 was found and removed"); else System.out.println("100 was not found"); t1.preOrder();

// End given functions testing

// Update test 1 - node not found if (t1.update(1000, 20) == true) System.out.println("1000 was changed to 20"); else System.out.println("1000 was not changed to 20");

// Update test 2 - node found if (t1.update(160, 25) == true) System.out.println("160 was changed to 25"); else System.out.println("160 was not changed to 25"); t1.preOrder();

// Update test 3 - node found and changed root if (t1.update(150, 75) == true) System.out.println("150 was changed to 75"); else System.out.println("150 was not changed to 75"); t1.preOrder();

// Math functions test System.out.println("Math functions test"); System.out.println(t1.findMin()); System.out.println(t1.findMax()); System.out.println(t1.calculateAverage()); System.out.println(t1.getNumberOfNodes());

// Balance test 1 if (t1.isBalanced()) System.out.println("Tree is balanced"); else System.out.println("Tree is not balanced");

// Balance test 2 t1.insert(171); t1.insert(172); t1.insert(173); t1.preOrder(); if (t1.isBalanced()) System.out.println("Tree is balanced"); else System.out.println("Tree is not balanced"); } }

}

Node Class:

public class Node { /* public int iData; // data item key public double dData; // data item public Node leftChild; // the node'e left child public Node rightChild; // Nodes right child*/ int data; public Node left; public Node right; public Node last; /* public void displayNode() { System.out.print('{'); System.out.print(iData); System.out.print(" , "); System.out.print(dData); System.out.print("} "); }*/ }