Styjun

I have come across this lab problem about implementing a remove method for generic type binary search tree.

I have implemented a binary search tree of generic type.

I have learnt the binary search tree remove algorithm, and I try to deal with 3 cases when the parent node has "0 child", " 1 child" or "2 children".

I implement the code to remove a node but keeps resulting in a stack overflow problem, and I cannot find where's wrong in my code.

Any help will be appreciated.

public class BinarySearchTree<T extends Comparable<T>> 

 private Node<T> _root; //Root node

 public class Node<T extends Comparable<T>> 
 public T get_value() return _value;

 public void set_value(T _value) this._value = _value;

 public Node<T> get_left() return _left;

 public void set_left(Node<T> _left) this._left = _left;

 public Node<T> get_right() return _right;

 public void set_right(Node<T> _right) this._right = _right;

 public Node<T> get_parent() return _parent;

 public void set_parent(Node<T> _parent) this._parent = _parent;

 T _value; // Node value
 Node<T> _left; // Left child

 Node<T> _right; // Right child
 Node<T> _parent; // Parent node

 public Node(T key, Node<T> parent, Node<T> left, Node<T> right) 
 _value = key;
 _left = left;
 _right = right;
 _parent = parent;
 
 
 // Remove a node from the BST
 private Node<T> remove(BinarySearchTree<T> bst, Node<T> z) 
 Node<T> delNode = null;
 if(bst._root == null)
 delNode = null;
 
 else
 Node<T> current = bst._root;
 // find the position to delete
 while(current!=null)
 int compare = z.get_value().compareTo(current.get_value());
 if(compare < 0)
 current = current.get_left();
 
 if(compare > 0)
 current = current.get_right();
 
 else
 // if node has two child,replace it with right minimum value
 if (current._left!=null && current._right!=null)
 delNode = current;
 Node<T> successor = minimumKey(current.get_right());
 current.set_value(successor.get_value());
 remove(successor._value);
 
 if (current._left!=null)
 delNode = current;
 remove(current._value);
 current._left.set_parent(current._parent);
 
 if (current._right!=null)
 delNode = current;
 remove(current._value);
 current._right.set_parent(current._parent);
 
 else
 delNode = current;
 remove(current._value);
 
 
 

 


 return delNode;

 
 // remove a node value
 public void remove(T key) 
 Node<T> z, node;
 if ((z = find(_root, key)) != null)
 if ( (node = remove(this, z)) != null)
 node = null;
 
 public Node<T> minimumKey(Node<T> current) 
 while (current._left != null) 
 current = current._left;
 
 return current;
 

You have an issue with your conditions. They should be:

 if(compare < 0) 
 current = current.get_left();
 else if(compare > 0) 
 current = current.get_right();
 else {
 ...

As it is now, if compare < 0 is true, you execute both current = current.get_left(); and the else clause.

I'm not sure that's the only issue with your remove method, though.