JAVA: Whats wrong with my code? Assignment was to implement print reverse, remov
ID: 3905690 • Letter: J
Question
JAVA: Whats wrong with my code?
Assignment was to implement print reverse, remove, and to print an actual tree for this binary search tree class. here is my output when i ran the tester class that i made. The reverse order isnt working, and getting an weird error when i try to remove. everything is compling okay though. have not gotten to printing the tree because i wanted to get the print reverse and remove out of the way first.
*** looking for tips, lines to fix/what i did wrong, please try to avoid changing all the work i did.
output:
code: if it isnt indented it is because when i post, all the indentations disappear.
public class MyTree{
private TreeNode root;
public MyTree(){
root=null;
}
public void remove(int data){
//implement this method to remove a node with the same data value
TreeNode focusNode = root;
TreeNode valueNode = null; // will be variable to keep track of the node containing value we are removing
if (root == null){} // cant remove anything if root is null
else
valueNode = removeHelper(focusNode, data);
// to delete node if it has 0-1 children
if (valueNode.getLeft() == null){
valueNode.setData(valueNode.getRight().getData()); //= valueNode.getRight().getData();
TreeNode temp = valueNode.getRight(); //valueNode.getRight().setData(null);
temp = null;
} else if (valueNode.getRight() == null){
valueNode.setData(valueNode.getLeft().getData()); //= valueNode.getLeft().getData();
TreeNode temp = valueNode.getLeft(); //valueNode.getLeft().setData(null);
temp = null;
}
// to delete if it has 2 children or the root
else if (valueNode.getLeft() != null && valueNode.getRight() != null){
valueNode.setData(getSuccessor(valueNode).getData()); //=getSuccessor(valueNode).getData();
TreeNode temp = getSuccessor(valueNode); //getSuccessor(valueNode).setData(null);
temp = null;
}
} // end method
// will find successor if valuenode has two children
private TreeNode getSuccessor(TreeNode node){
TreeNode temp = node.getRight(); // temp node is the one to the down>right of the one we are trying to replace
while(temp != null)
temp = temp.getLeft();
return temp;
}
// searches through tree until it finds the node with the value, then returns the node
private TreeNode removeHelper(TreeNode node, int data){
if (node.getData() == data)
return node;
else if (data<node.getData())
return removeHelper(node.getLeft(), data);
else return removeHelper(node.getRight(), data);
} // end method
public void printReverse(){
//implement this method to print data in descending order
printReverseHelper(root);
}
private void printReverseHelper(TreeNode node){
if (node != null){
printHelper(node.getRight());
System.out.println(node.getData());
printHelper(node.getLeft());
}
}
//public void display(){
//implement to display the tree structure
//}
public boolean isEmpty(){ return root==null;}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(TreeNode node){
if(node==null) return 0;
else return 1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
public boolean search(int data){
return searchHelper(root, data);
}
private boolean searchHelper(TreeNode node, int data){
if(node==null) return false;
if(node.getData()==data) return true;
else if(node.getData()<data)
return searchHelper(node.getRight(),data);
else
return searchHelper(node.getLeft(), data);
}
public void add(int data){
root=addHelper(root, data);
}
private TreeNode addHelper(TreeNode node, int data){
if(node==null) node=new TreeNode(data);
else if(data<=node.getData()) //or call compareTo method
node.setLeft(addHelper(node.getLeft(), data));
else
node.setRight(addHelper(node.getRight(), data));
return node;
}
public void printInorder(){
printHelper(root);
}
private void printHelper(TreeNode node){
if(node!=null){
printHelper(node.getLeft());
System.out.println(node.getData());
printHelper(node.getRight());
}
}
}
Explanation / Answer
Given below is the fixed code for the question.
You need to call the printReverseHelper() inside printReverseHelper() instead of printHelper().
Also for remove() you need to keep track of the parent node, since when deleting leaf nodes, it become important to know the parent and set the reference to null in the parent. So modified code accordingly. Also we need to chekc if root is being deleted. Please check with this fixed code and let me know if any issues.
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
Please do rate the answer if it was helpful. Thank you
public class MyTree{
private TreeNode root;
public MyTree(){
root=null;
}
public void remove(int data){
//implement this method to remove a node with the same data value
TreeNode parent = null;
TreeNode valueNode = root; // will be variable to keep track of the node containing value we are removing
while(valueNode != null)
{
if(valueNode.getData() == data)
break;
else
{
parent = valueNode;
if(data < valueNode.getData())
valueNode = valueNode.getLeft();
else
valueNode = valueNode.getRight();
}
}
if(valueNode == null) //could not locate data
return;
// if it has 0-1 right child
if (valueNode.getLeft() == null ){
if(valueNode == root) //deleting root?
{
root = valueNode.getRight();
}
else
{
if(valueNode == parent.getLeft()) //if node to be deleted is left child of its parent
parent.setLeft(valueNode.getRight());
else
parent.setRight(valueNode.getRight());
}
} else if (valueNode.getRight() == null){ //node has 0-1 left child
if(valueNode == root) //deleting root?
{
root = valueNode.getLeft();
}
else
{
if(valueNode == parent.getLeft()) //if node to be deleted is left child of its parent
parent.setLeft(valueNode.getLeft());
else
parent.setRight(valueNode.getLeft());
}
}
// to delete if it has 2 children or the root
else if (valueNode.getLeft() != null && valueNode.getRight() != null){
TreeNode successor = getSuccessor(valueNode);
int dataCopy = successor.getData();
//use recursive call to remove the successor
remove(successor.getData());
//now copy over the successor data onto valueNode
valueNode.setData(dataCopy);
}
} // end method
// will find successor if valuenode has two children
private TreeNode getSuccessor(TreeNode node){
TreeNode temp = node.getRight(); // temp node is the one to the down>right of the one we are trying to replace
while(temp != null)
temp = temp.getLeft();
return temp;
}
// searches through tree until it finds the node with the value, then returns the node
private TreeNode removeHelper(TreeNode node, int data){
if (node.getData() == data)
return node;
else if (data<node.getData())
return removeHelper(node.getLeft(), data);
else return removeHelper(node.getRight(), data);
} // end method
public void printReverse(){
//implement this method to print data in descending order
printReverseHelper(root);
}
private void printReverseHelper(TreeNode node){
if (node != null){
printReverseHelper(node.getRight());
System.out.println(node.getData());
printReverseHelper(node.getLeft());
}
}
//public void display(){
//implement to display the tree structure
//}
public boolean isEmpty(){ return root==null;}
public int size(){
return sizeHelper(root);
}
private int sizeHelper(TreeNode node){
if(node==null) return 0;
else return 1+sizeHelper(node.getLeft())+sizeHelper(node.getRight());
}
public boolean search(int data){
return searchHelper(root, data);
}
private boolean searchHelper(TreeNode node, int data){
if(node==null) return false;
if(node.getData()==data) return true;
else if(node.getData()<data)
return searchHelper(node.getRight(),data);
else
return searchHelper(node.getLeft(), data);
}
public void add(int data){
root=addHelper(root, data);
}
private TreeNode addHelper(TreeNode node, int data){
if(node==null) node=new TreeNode(data);
else if(data<=node.getData()) //or call compareTo method
node.setLeft(addHelper(node.getLeft(), data));
else
node.setRight(addHelper(node.getRight(), data));
return node;
}
public void printInorder(){
printHelper(root);
}
private void printHelper(TreeNode node){
if(node!=null){
printHelper(node.getLeft());
System.out.println(node.getData());
printHelper(node.getRight());
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.