recursive binary search tree remove method

Question

First off, this is homework, so putting that out there.

I'm supposed to implement a binary search tree with specific methods:

void insert(String), boolean remove(String), and boolean find (String).

I have been able to successfully program and test the insert and find methods but am having difficulty with the remove.

What is going on in my program is the remove isn't actually removing anything from the tree and I believe this is because its only referencing the local creation of the current node but I could be wrong. I think I can implement the logic of the different cases I need to test (might need help with the deleting a node with two children case but I think I get it conceptually) am mainly trying to understand what I need to do differently to reference the tree properly in the

current = null; // case

Here is what I got so far:

public boolean remove(String title)
{
    return remove(root, title);
}
private boolean remove(BSTNode current, String title)
{
    if (current == null)
    {
        return false;
    }
    if (current.data == title)
    {
    if (current.left_child !=null && current.right_child != null)
    {
        return true;  // returning true since I haven't finished writing this case
    }
    else if (current.left_child == null && current.right_child == null)
        {
        current = null;  // this should remove the node from tree but it doesn't
        return true; 
    }

    else if (current.left_child != null && current.right_child == null)
    {
        current = current.left_child;    // don't think this is right
        return true;
    }
    else if (current.right_child != null && current.left_child == null)
    {
        current = current.right_child;   // not sure about this
        return true;
    }

    }
root = current;
if (title.compareToIgnoreCase(current.data) == -1)
{
    return remove(current.left_child, title);
}
    else 
{
    return remove(current.right_child, title);
}
}

Any knowledge is much appreciated.

Answer 1

A node is referenced by it's parent (except for the root, that node is referenced by your BST itself). In order to remove a node from the tree, you need to set that reference in the parent node to null.

What you're trying to do now is something like:

Before:
parent.left ---> node <--- current

After setting current = null:
parent.left ---> node      current ---> null

that is, current references null, but that does not change the parent (only that local variable).

In your remove method you need to pass the parent along as well (or handle both children in the call for the parent, whatever you like better).

By the way: never, ever compare strings with ==, see for instance this question.

---

How to find the node and it's parent without explicitly storing the parent in each node:

I would say it is simpler to do this in a loop, rather than with recursion, but both would work. In a loop:

BSTNode parent = null;
BSTNode current = root;
boolean found = false;
while (!found && current != null) {
    int compare = title.compareToIgnoreCase(current.data);
    if (compare == 0) {
        found = true;
    } else {
        parent = current;
        if (compare < 0) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
}
if (!found) {
    // title was not found
} else if (parent == null) {
    // found the root
} else {
    // found another node
}

By recursion is annoying, because you want a method that returns both the node and it's parent. You will need some simple inner class to solve this:

private class NodeAndParent {
    public BSTNode node;
    public BSTNode parent;
    public NodeAndParent(BSTNode node, BSTNode parent) {
        this.node = node;
        this.parent = parent;
    }
}

private boolean find(String title, NodeAndParent current) {
    if (current.node == null) {
        return false; // not found
    } else {
        int compare = title.compareToIgnoreCase(current.node.data);
        if (compare == 0) {
            return true; // found
        } else {
            current.parent = current.node;
            if (compare < 0) {
                current.node = current.node.left;
            } else {
                current.node = current.node.right;
            }
        }
    }
}

private boolean remove(String title) {
    NodeAndParent nodeAndParent = new NodeAndParent(root, null);
    boolean found = find(title, nodeAndParent);
    if (!found) {
        // title was not found
    } else if (nodeAndParent.parent == null) {
        // found the root
    } else {
        // found another node
    }
}