Deleting a node and returning the deleted node's value in a Binary Search Tree?

Question

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;
    }

}

score 2 · Accepted Answer · answered Nov 22 '16 at 01:55

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;
}

score 0 · Answer 2 · edited Apr 13 '17 at 12:45

In Java, you can endeavor to return multiple values, via an object of a class defined just for that aggregate. See How are multiple values returned in Java?.

Alternately, you can redesign your private method to do the work of assigning the new tree to the parent, by passing additional parameter. Untested, but something like this:

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

private void setParentLeft ( Node parent, Node node ) {
    if ( parent == null )
       root = node;
    else
       parent.left = node;    
}

private int popMin ( Node parent, Node node ) {
    if ( node.left == null ) {
        if ( node.right != null ) { //if a right child exists
            size--;
            setParentLeft ( parent, node.right );
        }
        else {
            size--;
            setParentLeft ( parent, null );
        }
        return node.key;
    } else {
        return popMin ( node, node.left );
    }
}

in this case, that also has the advantage of now being tail recursion, which we can let the compiler work on, or, manually, here a simple non-recursive version:

private int popMin ( Node parent, Node node ) {
    for (;;) {
        if ( node.left == null ) {
            if ( node.right != null ) { //if a right child exists
                size--;
                setParentLeft ( parent, node.right );
            }
            else {
                size--;
                setParentLeft ( parent, null );
            }
            return node.key;
        }

        parent = node;
        node = node.left;
    }
}

Deleting a node and returning the deleted node's value in a Binary Search Tree?

2 Answers2