I am having a difficult time troubleshooting a BinaryTree program in Java. The p
ID: 3837729 • Letter: I
Question
I am having a difficult time troubleshooting a BinaryTree program in Java. The program runs but I can't get the expected output. The existing program cannot be modified(runs just fine). Only, add your functions to get the expected output below.
Here are the functions to be added to the Binary Tree Class to get the expected output:
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:
- If both of its subtrees are balanced
- The height of its left subtree differs from the height of its right subtree by at most 1.
Here is my the output:
InOrder:
50
100
150
175
200
PreOrder:
100
50
175
150
200
150 Found
10 Not Found
100
50
175
150
160
155
158
170
200
200 was found and removed
150
50
175
160
155
158
170
200
1 was found and removed
155 was found and removed
158
50
175
160
170
200
100 was found and removed
160
50
175
170
200
1000 was not changed to 20
160 was changed to 25
25
50
175
170
200
150 was changed to 75
25
50
175
170
200
Math functions test
50
200
124.0
5
Tree is balanced
25
50
175
170
171
172
173
200
Tree is not balanced
This is the Expected Output:
InOrder:
50
100
150
175
200
PreOrder:
100
50
175
150
200
150 Found
10 Not Found
100
50
175
150
160
155
158
170
200
200 was found and removed
100
50
175
150
160
155
158
170
1 was not found
155 was found and removed
100
50
175
150
160
158
170
100 was found and removed
150
50
175
160
158
170
1000 was not changed to 20
160 was changed to 25
150
50
25
175
170
158
150 was changed to 75
158
50
25
75
175
170
Math functions test
25
175
108.833333
6
Tree is balanced
158
50
25
75
175
170
171
172
173
Tree is not balanced
CODE:
public static void main(String[] args) {
// TODO code application logic here
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");
}
}
Binary tree class:
public class BinaryTree {
// insert function
// 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 node’s 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;
while (current != null)
{
successorParent = successor;
successor = current;
current = current.left;
}
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 successor’s right stays that way even
// after successor replaces the removed node.
return successor;
}
// Traversing a Tree
public void display()
{
inOrder(root);
}
void preOrder()
{
preOrder(root);
}
void preOrder(Node current)
{
if (current != null)
{
System.out.println(current.data);
/*display*/preOrder(current.left);
/*display*/preOrder(current.right);
}
}
void inOrder()
{
inOrder(root);
}
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);
}
}
Node Class:
public class Node {
int data;
public Node left;
public Node right;
public Node last;
Explanation / Answer
Hello,
The remove method was not getting updated correctly. So i have added newRemove(int key) method in BinaryTree.java instead of public boolean remove(int n)
I hope this helps.Please reply if you have any queries.
---------------------------------------------------
Main.java
---------------------------------------------------
package bst;
public class Main {
public static void main(String[] args) {
// TODO code application logic here
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.newRemove(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.newRemove(1) == true)
System.out.println("1 was found and removed");
else
System.out.println("1 was not found");
// One child remove test
if (t1.newRemove(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.newRemove(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.java
---------------------------------------------------
package bst;
public class Node {
int data;
public Node left;
public Node right;
public Node last;
}
---------------------------------------------------
BinaryTree.java
---------------------------------------------------
package bst;
public class BinaryTree {
// insert function
// 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 node’s 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;
while (current != null)
{
successorParent = successor;
successor = current;
current = current.left;
}
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 successor’s right stays that way even
// after successor replaces the removed node.
return successor;
}
// Traversing a Tree
public void display()
{
inOrder(root);
}
void preOrder()
{
preOrder(root);
}
void preOrder(Node current)
{
if (current != null)
{
System.out.println(current.data);
/*display*/preOrder(current.left);
/*display*/preOrder(current.right);
}
}
void inOrder()
{
inOrder(root);
}
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);
}
}
boolean update(int current, int newData){
Node foundNode = search(current);
if(foundNode != null){
newRemove(current);
insert(newData);
return true;
}
return false;
}
int findMin(){
Node current = root;
if(current == null){
return -1;
}
while(current.left != null){
current = current.left;
}
return current.data;
}
/**
* method to find maximum
* @return
*/
int findMax(){
Node current = root;
if(current == null){
return -1;
}
while(current.right != null){
current = current.right;
}
return current.data;
}
/**
* to get number of Nodes
* @return
*/
int getNumberOfNodes(){
Node current = root;
return getNumberOfNodes(current);
}
/**
* recursive function to get number of nodes
* @param node
* @return
*/
int getNumberOfNodes(Node node){
if (node == null) //empty
return 0;
if (node.left == null && node.right == null) //only parent node
return 1;
else
return getNumberOfNodes(node.left) + getNumberOfNodes(node.right)+1;
}
double calculateAverage(){
Node current = root;
if( current != null){
sumOfNodes(current);
getNumberOfNodes();
return sumOfNodes(current)/getNumberOfNodes();
}else{
return 0.0;
}
}
/**
* recursive function to
* get sum of data in all nodes
* @param current
* @return
*/
private double sumOfNodes(Node current) {
if(current!=null){
return current.data+ sumOfNodes(current.left)+sumOfNodes(current.right);
}
return 0.0;
}
/**
* method to check if tree is balanced
* @return
*/
boolean isBalanced(){
Node current = root;
if(current == null){
return false;
}else{
return isBalanced(current);
}
}
/**
* recursive fucntion to check balance
* @param current
* @return
*/
private boolean isBalanced(Node current) {
int leftHeight,rightHeight;
if (current == null)
return true;
leftHeight = getHeight(current.left);
rightHeight = getHeight(current.right);
if (Math.abs(leftHeight - rightHeight) <= 1
&& isBalanced(current.left)
&& isBalanced(current.right))
return true;
return false;
}
private int getHeight(Node node) {
if(node == null){
return 0;
}
else{
return Math.max(getHeight(node.left),getHeight(node.right))+1;
}
}
/**
* this new remove method is added as old method doesnt update the tree
* @param searchElement
* @return
*/
boolean newRemove(int searchElement)
{
Node found = search(searchElement);//search for the searchKey
root = newRemoveFunc(root, searchElement);
if(found == null){//if there is no such element
return false;
}
return true;
}
/**
* recursive fucntion to remove node from tree
* @param root
* @param key
* @return
*/
Node newRemoveFunc(Node root, int key)
{
if (root == null) return root;
if (key<root.data)//less than current node then traverse to left
root.left = newRemoveFunc(root.left, key);
else if (key>root.data)//greater than current node then traverse to right
root.right = newRemoveFunc(root.right, key);
else
{
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.data = getMinValueUsingNode(root.right);
root.right = newRemoveFunc(root.right, root.data);
}
return root;
}
/**
* method to get minimum value from current node
* @param root
* @return
*/
int getMinValueUsingNode(Node root)
{
int minimum = root.data;
while (root.left != null)
{
minimum = root.left.data;
root = root.left;
}
return minimum;
}
}
-----------------------------------------
OUTPUT
-----------------------------------------
InOrder:
50
100
150
175
200
PreOrder:
100
50
175
150
200
150 Found
10 Not Found
100
50
175
150
160
155
158
170
200
200 was found and removed
100
50
175
150
160
155
158
170
1 was not found
155 was found and removed
100
50
175
150
160
158
170
100 was found and removed
150
50
175
160
158
170
1000 was not changed to 20
160 was changed to 25
150
50
25
175
170
158
150 was changed to 75
158
50
25
75
175
170
Math functions test
25
175
108.83333333333333
6
Tree is balanced
158
50
25
75
175
170
171
172
173
Tree is not balanced
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.