Remove the minimum value in a binary search tree

Question

I understand the algorithms but I am not sure how to put it into actual codes. Please help! And also please explain in details. I really want to understand this besides just copying down the answer. ;)

Here are my codes:

 public boolean getLeftChild(){
    Node insertNode = root;
    while(insertNode!=null){
        insertNode = insertNode.left;
    }
    return true;
}
public Boolean removeMin(){
    Node insertNode = root;
    Node parentNode =root;

        if (insertNode.left ==null){
            insertNode.right = parentNode;
            insertNode = null;

        }else if (getLeftChild() ==true && insertNode.right != null){
            insertNode.left = null;
        }else{
            parentNode.left = insertNode.right;

    }
        return true;
}

1) For better help sooner, post an [SSCCE](http://sscce.org/). 2) Try describing a) What you expected to happen b) What actually happened, and for utility c) Why you expected (a) to happen. — Andrew Thompson, Nov 10 '13 at 23:16
Also `getLeftChild` always returns true. What is its purpose? — NG., Nov 10 '13 at 23:18

score 1 · Answer 1 · answered Nov 10 '13 at 23:34

First things first: For trees I highly recommend recursion.

Just one example:

getSmallestNode(Node node){
     if(node.left != null){
         return getSmallestNode(node.left)
     }

     return node;
}

For the deletion, there can be two cases if you want do delete the smallest (and therefore the "most left leaf" child) of a binary tree.

Case 1: The leaf has no child nodes, in that case just set the according entry in the parent to null (mostLeftChild.getParent().left = null)

Case 2: The leaf has a right child node (there can't be a left child node because that means there would be a smaller node and your currently selected node isn't the smallest) in that case you replace the current left node with the smallest node of the right subtree mostLeftChild.getParent().left = getSmallestFromSubtree(mostLeftChild.right)

So now to make that into code, it could look something like this (No guarantee that it really works)

public Node deleteSmallest(Node node){
    // haven't reached leaf yet
    if(node.left != null{
        return deleteSmallest(node.left)
    }

    // case 1, no child nodes
    if(node.right == null){
        node.getParent().left = null;
    } else { // case 2, right child node
        node.getParent().left = deleteSmallest(node.right)
    }

    return node;
}

And you would call it with deleteSmallest(root)

I don't know how your `Node` class is implemented but in each node I would at least store four values. 1. the parent node (only null for the root) 2. the left child 3. the right child 4. the value of the node. — , Nov 10 '13 at 23:50
oh okay, there are only left node, right node, and the value in my Node class. I created "Node root" in my BST class. So, the codes would node.parent.left == null? — user2892181, Nov 11 '13 at 04:35

Remove the minimum value in a binary search tree

1 Answers1