Why Is My Binary Search Tree Delete Recursion Not Ending?

Question

I am trying to implement a binary search tree using Java. One of the functions that I want to create is the delete function. This will consists of two methods, one called delete and the other called getNodeToDelete. The getNodeToDelete method is a helper function for the delete method.

The getNodeToDelete method is recursive, and basically returns the node that the user wants to delete from the tree. Using the node that is returned from this getNodeToDelete method, the non-recursive delete method basically makes important decisions on how to delete this node depending on different cases (e.g. is it a leaf node, is it a root node etc.).

This is the non-recursive delete method:

 /**
     * Deletes the relevant node (according to the key inputted by the user), using two helper functions:
     * getNodeToDelete(int deleteKey, Node root) and getMinRight(Node nodeToDelete).
     * @param key
     */
    public void delete(int key) {
        if (root.left == null && root.right == null) {
            if (root.key == key) {
                root = null;
                System.out.println("It reached the first if-statement of the delete() method.");
            }
        }
        Node nodeToDelete = getNodeToDelete(key, root); //The node that is returned from its helper function.
        System.out.println("This is the node to delete: " + nodeToDelete.key);
        if (nodeToDelete.right == null && nodeToDelete.left == null) {  //If the nodeToDelete is a leaf.
            nodeToDelete = null;
//            System.out.println("This is the key of the deleted node: " + nodeToDelete.key);
            return;
        } else if (nodeToDelete.right == null) {  //If the nodeToDelete has an empty right tree.
            Node immediateLeftNode = nodeToDelete.left;
            nodeToDelete.key = immediateLeftNode.key;
            nodeToDelete.left = immediateLeftNode.left;
            nodeToDelete.right = immediateLeftNode.right;
        } else if (nodeToDelete.right != null) {  //If the nodeToDelete has a non-empty right tree
            if (nodeToDelete.right.left == null) {  //If the left branch of the right branch of nodeToDelete is empty.
                nodeToDelete.key = nodeToDelete.right.key;
                nodeToDelete.right = nodeToDelete.right.right;
            } else {
                Node replacementNode = getMinRight(nodeToDelete);
                nodeToDelete.key = replacementNode.key;
            }
        }
    }

And this is the recursive getNodeToDelete method:

/**
     * Assumption: the key does exist in the tree.
     * Returns the node that the user wants to delete, based on the key that the user inputs.
     * @param deleteKey
     * @param startingRoot
     * @return
     */
    public Node getNodeToDelete(int deleteKey, Node startingRoot) {
        if (startingRoot == null) {
            return null;
        }

        if (startingRoot.key == deleteKey) {
            return startingRoot;
        }

        if (deleteKey < startingRoot.key) {
            getNodeToDelete(deleteKey, startingRoot.left);
        }

        getNodeToDelete(deleteKey, startingRoot.right);
        return startingRoot;
    }

The problem is, the helper function, getNodeToDelete, traverses down the tree to one of its nodes, for example, the leaf node of value -12. Then it returns that node, but the recursive method getNodeToDelete seems to not end. It then traverses back up to the root node again, always resulting in the returned value being the root node.

I know that there are many different approaches to implementing a binary search tree in Java, but this recursion problem is bothering me and I really want to know the reason behind the failure of this.

Please let me know if you need more clarification. Thanks

Answer 1

Someone answered my question before they deleted it, but their answer definitely helped me in finding a solution. So, thank you whoever it was.

Basically, my recursion (in the recursive method, getNodeToDelete), was always returning my root node because I was not returning the results of the recursion. Thus, discarding my wanted data instead of letting it recur back to me. This is quite difficult to explain but basically, this is the getNodeToDelete method after fixing:

/**
     * Assumption: the key does exist in the tree.
     * Returns the node that the user wants to delete, based on the key that the user inputs.
     * @param deleteKey
     * @param startingRoot
     * @return
     */
    public List<List> getNodeToDelete(int deleteKey, Node startingRoot, Node parentNode, String directionFlag) {
        List<Node> nodes = new ArrayList<>();
        nodes.add(startingRoot);
        nodes.add(parentNode);

        List<List> nodeData = new ArrayList<>();
        nodeData.add(nodes);
        List<String> direction = new ArrayList<>();
        direction.add(directionFlag);

        nodeData.add(direction);

        if (startingRoot == null) {
            return null;
        }

        if (startingRoot.key == deleteKey) {
            System.out.println("This is node that is FINALLY RETURNED " + startingRoot.key);
            return nodeData;
        }

        if (deleteKey < startingRoot.key) {
            System.out.println("This is node that is returned " + startingRoot.key);
            return getNodeToDelete(deleteKey, startingRoot.left, startingRoot, "left"); //Added return statement here.
        }

        System.out.println("This is node that is returned " + startingRoot.key);
        return getNodeToDelete(deleteKey, startingRoot.right, startingRoot, "right");  //Added return statement here.
    }

Other than couple other things that I changed, which were because of some errors in my delete function, the thing that allowed my getNodeToDelete method to return the node that the user wanted to delete, was by adding return statements in the places that are commented with Added return statement here in the above code snippet.

This is still quite mind-blowing to me as to why I overlooked this important step behind recursion, so I need to think on it more. But, basically, the moral of the story is, make sure to actually return your results from the recursion, instead of simply calling on the function recursively!