Binary Search Tree – Deleting a Node and Returning Its Value

binary treedata structuresjava

Hi I have a programming project where I'm basically using a Binary Search Tree to implement a min/max priority queue. I'm having trouble with the popMin/popMax methods. I get how to get the minimum/maximum node and remove a node, but I'm having trouble doing both with a single recursive method.

I don't understand how I can return null value to assign to the parent node's left value, and also return the minimum value to the original method caller.

Right now I'm just using a class variable min to record the minimum, but I'm not sure if that's absolutely necessary. My node class is not allowed a parent data member.

Here is my code:

private int min;

public int removeMin() {

    if (root == null) { //if Queue is empty
        System.out.println("Queue is empty");
        return 0;
    }
    root = removeMin(root);

    return min;

}


private Node removeMin(Node n){
    if (n.left == null) {
        min = n.key;
        if (n.right != null){ //if a right child exists
            size--;
            return n.right;
            }
        else {
            size--;
            n = null;
            return n;
        }
    } else {
        n.left = removeMin(n.left);
        return n;
    }

}

Best Answer

Ditch the recursion. You usually need recursion when dealing with trees because you need to visit all the paths, but here you only visit one child in each level - you can do it with a loop. Also, while your code looks like it can update nodes at any level while going up the recursion, it actually only changes one node - the parent of the node with minimal value. Since you detect that that node needs to be change one level after you visit it(when you reach the end of the leftmost path) you don't need to bubble that up - you can just keep the parent level in a variable:

public int removeMin() {
    if (root == null) { //if Queue is empty
        System.out.println("Queue is empty");
        return 0;
    }

    if (root.left == null) { // Edge case - no left child, root is the min
        int min = root.key;
        if (root.right == null) {
            root = null;
        } else {
            root = root.right;
        }
        return min;
    }

    // Start going left
    Node parent = root;
    Node node = parent.left;

    while(node.left != null) {
        parent = node;
        node = parent.left;
    }

    // node.left is null, so node is the min
    parent.right = node.right; // which could be null - it works either way
    return node.key;
}
Related Topic