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. 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
– Andrew Thompson, Commented Nov 10, 2013 at 23:16
Also getLeftChild always returns true. What is its purpose? — NG.
– NG., Commented Nov 10, 2013 at 23:18

user2275786 · Accepted Answer · 2013-11-10 23:34:13Z

1

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)

answered Nov 10, 2013 at 23:34

user2275786

Sign up to request clarification or add additional context in comments.

3 Comments

user2892181 Over a year ago

what would be the getParent() method

user2275786 Over a year ago

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.

user2892181 Over a year ago

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?

Collectives™ on Stack Overflow

Remove the minimum value in a binary search tree

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related