Problems with Binary Tree node removal Java

Question

I wanted to try and implement my own BST as an exercise, but I am stuck on the node removal. I cannot figure out why it doesn't work in some cases. I took the algorithm from a book, but when I test it with random elements, there are cases in which it does not remove the element, or even messes up their order so they are no longer sorted. What am I doing wrong and what would be a better way to accomplish this?

NOTE: All of the println() statements in the methods are there only for debugging purposes

class TreeNode<T extends Comparable<T>> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;
    TreeNode<T> parent;

    TreeNode(T data) {
        this.data = data;
    }

    boolean hasBothChildren() {
        return hasLeftChild() && hasRightChild();
    }

    boolean hasChildren() {
        return hasLeftChild() || hasRightChild();
    }

    boolean hasLeftChild() {
        return left != null;
    }

    boolean hasRightChild() {
        return right != null;
    }

    boolean isLeftChild() {
        return this.parent.left == this;
    }

    boolean isRightChild() {
        return this.parent.right == this;
    }
}

public class BinaryTreeSet<T extends Comparable<T>> {
    private TreeNode<T> root;

    private void makeRoot(T element) {
        TreeNode<T> node = new TreeNode<T>(element);
        root = node;
    }

    private TreeNode<T> find(T element) {
        TreeNode<T> marker = root;
        TreeNode<T> found = null;

        while (found == null && marker != null) {
            int comparator = (marker.data.compareTo(element));

            if (comparator > 0)
                marker = marker.left;
            else if (comparator < 0)
                marker = marker.right;
            else
                found = marker;
        }

        return found;
    }

    private TreeNode<T> max(TreeNode<T> root) {
        TreeNode<T> currentMax = root;

        while (currentMax.hasRightChild()) {
            currentMax = currentMax.right;
        }

        return currentMax;
    }

    // returns the inorder predecessor of node
    private TreeNode<T> predecessor(TreeNode<T> node) {
        return max(node.left);
    }

    // removes a given node with 0 or 1 children
    private void removeNode(TreeNode<T> node) {
        if (!node.hasChildren()) {
            System.out.println("node with no children");
            if (node.isLeftChild())
                node.parent.left = null;
            else
                node.parent.right = null;
        }
        else {
            System.out.println("node with 1 child");
            if (node.isRightChild()) {
                if (node.hasLeftChild())
                    node.parent.right = node.left;
                else if (node.hasRightChild())
                    node.parent.right = node.right;
            }
            else if (node.isLeftChild()) {
                if (node.hasLeftChild())
                    node.parent.left = node.left;
                else if (node.hasRightChild())
                    node.parent.left = node.right;
            }
        }

        node = null;
    }

    public BinaryTreeSet() {
        root = null;
    }

    public void addElement(T element) {
        if (root == null)
            makeRoot(element);
        else {
            TreeNode<T> marker = root;
            TreeNode<T> node = new TreeNode<T>(element);
            boolean done = false;

            while(!done) {
                int comparator = marker.data.compareTo(element);
                if (comparator > 0) {
                    if (marker.hasLeftChild())
                        marker = marker.left;
                    else {
                        marker.left = node;
                        done = true;
                    }
                }
                else if (comparator < 0) {
                    if (marker.hasRightChild())
                        marker = marker.right;
                    else {
                        marker.right = node;
                        done = true;
                    }
                }
                else
                    return;

                node.parent = marker;
            }
        }
    }

    public boolean contains(T element) {
        boolean found = (find(element) == null)? false : true;
        return found;
    }

    public boolean removeElement(T element) {
        TreeNode<T> node = find(element);
        if (node == null)
            return false;

        // removal of a node with no children
        if (!node.hasChildren()) {
            if (node.isLeftChild()) {
                node.parent.left = null;
            }
            else if (node.isRightChild()) {
                node.parent.right = null;
            }
        }

        // removal of a node with both children
        else if (node.hasBothChildren()) {
            TreeNode<T> pred = predecessor(node);
            T temp = pred.data;
            pred.data = node.data;
            node.data = temp;
            removeNode(pred);
        }

        // removal of a node with only 1 child
        else {
            if (node.isRightChild()) {
                if (node.hasLeftChild())
                    node.parent.right = node.left;
                else if (node.hasRightChild())
                    node.parent.right = node.right;
            }
            else if (node.isLeftChild()) {
                if (node.hasLeftChild())
                    node.parent.left = node.left;
                else if (node.hasRightChild())
                    node.parent.left = node.right;
            }

        }

        node = null;
        System.out.println("item removed: " + !contains(element));
        return true;
    }
}

Answer 1

Found the bug that was causing me headaches. The problem was in the cases where I remove nodes with 0 or 1 child. I was not updating their parent nodes, so that messed up with the code. So, instead of, for example

if (node.hasLeftChild())
    node.parent.right = node.left;

I should have written

if (node.hasLeftChild()) {
    node.parent.left = node.left;
    node.left.parent = node.parent;
}

in all cases where I deal with a single child. Also, I forgot to update the root, when the root is the target of the removeElement() function. However, as it currently stands, I feel I have a lot of repetition in the code. I am yet to come up with a more elegant solution.

EDIT: There are other minor bugs as well, mainly in the isRightChild() and isLeftChild() functions, resulting in NullPointerException if the node in question does not have a parent.

Answer 2

please add following Method into BinaryTreeSet Class and call it, which will show you current element list with Left/Right prefix.

 boolean rootOncePrint = true;
    public void printAllTree(TreeNode<T> startNode){
        if(startNode == null) return;
        //System.out.println(startNode.data);
        if(rootOncePrint){
            System.out.println("Root : " + startNode.data);
            rootOncePrint = false;
        }

        if(startNode.hasChildren()){
            if(startNode.hasLeftChild()){
                printAllTree(startNode.left);
            } 
            if(startNode.hasRightChild()){
                printAllTree(startNode.right);
            }

        }
        if(startNode != root){
            T parentValue = startNode.parent.data;
            T dataValue = startNode.data; 
            System.out.println(startNode.data + ((parentValue.compareTo(dataValue) > 0)?"L":"R"));
        }

    }

After Add this code, try to add/remove element into BinaryTreeSet so you will get to know what's going on.