Binary search tree deletion method error

Question

I am trying to write a method which recursively deletes a node from a binary search tree. I understand the algorithm, but my code is currently returning an error. When I try to delete a leaf node, i.e. a node which has no children, it deletes that node but also the topmost node of the tree.

I already have methods which to find the head of a node, getValue(), as well as finding the left and right subtrees, getLeft() and getRight(). I also have the method isEmpty() which checks to see if a tree is empty.

This is my code currently, where x is the node to be deleted and a is a binary search tree:

 public static Tree delete(int x, Tree a) {
        if (a.isEmpty()) {
            return new Tree();
        } if (x>a.getValue()) {
            return delete(x, a.getRight());
        } else if (x<a.getValue()) {
            return delete(x, a.getLeft());
        } else {
            if (a.getLeft().isEmpty()&&a.getRight().isEmpty()) {
                return new Tree();
            } if (a.getRight().isEmpty()) {
                return delete(x, a.getLeft());
            } if (a.getLeft().isEmpty()) {
                return delete(x, a.getRight());
            } else {
                return new Tree(); //not yet completed
            }
        }
    }

Can anyone give me any clues as to why this would be happening? Thanks in advance

Edit: Here is the code which eventually worked if anyone happens to stumble across this question

public static Tree delete(int x, Tree a) {
        if (a.isEmpty()) {
            return new Tree();
        } if (x>a.getValue()) {
            return new Tree(a.getValue(), a.getLeft(), delete(x, a.getRight()));
        } else if (x<a.getValue()) {
            return new Tree(a.getValue(), delete(x, a.getLeft()), a.getRight());
        } else {
            if (a.getLeft().isEmpty()&&a.getRight().isEmpty()) {
                return new Tree();
            } if (a.getRight().isEmpty()) {
                return new Tree(a.getLeft().getValue(), delete(a.getLeft().getValue(), a.getLeft()), a.getRight());
            } if (a.getLeft().isEmpty()) {
                return new Tree(a.getRight().getValue(), a.getLeft(), delete(a.getRight().getValue(), a.getRight()));
            } else {
                 return new Tree(max(a.getLeft()), delete(max(a.getLeft()), a.getLeft()), a.getRight());
            }
        }
    }

Answer 1

This method returns an empty tree instead of setting left or right as empty. This is why you think it's deleting the top node. Also it doesn't look like it handles deleting the node itself, only child nodes.

Answer 2

You never actually delete anything. There are two ways to do this.

1. Making a structureal copy of the tree until the node to be deleted and then take one of the children and insert the other to the chosen child the result of the insert is the result of the tree.

2. Finding the parent of the node to be deleted and mutate the accessor to the node to be one of the children and then add the other child subtree to the parent tree. Basically here you have a tree class that handles insertion and which has a root. Deleting the root is a special case with rebinding instead of altering a node.

If you are making a backtracking algorithm where going back to a previous tree is needed #1 is the only choice and it will share as much structure with the previous version of the tree. If you want to iterate and update a data structure to reflect something where you never need th eprevious state #2 is the best choice.