remove method for generic type binary search tree result in stack overflow problem

Question

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;
    }
}

Answer 1

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.