1
\$\begingroup\$

I have implemented this delete function for BST. Tt takes care of all the three cases, deleting node with 0, 1, or 2 children.

I have added comments throughout to explain my decisions. Is it sloppy or acceptable? Will I get full marks if this was a question in an exam to implement the delete function of a BST?

//I am having the node start parameter, so I can specify from where the
//deletion starts. So I can use it for recursion for the third case,
//where the node to be deleted has 2 children.
public void delete(Node start, int data) {
    if(root == null) return;

    /*If I want to call this method from any other class, I will pass in
    null as the start node, since I don't have reference to the root in 
    that class.
    I have this start parameter because in the case of a node having 2
    children, I am calling this method recursivly to delete, but I don't
    want to start from the root in that case. See below, last else */
    Node parent = start == null ? root : start;
    Node current = parent;
    boolean isLeftNode = false;

    while(data != current.getData() && current != null) {
        parent = current;

        if(data < current.getData()) {
            current = current.getLeftNode();
            isLeftNode = true;
        }
        else {
            current = current.getRightNode();
            isLeftNode = false;
        }
    }

    //If not found.
    if(current == null) return;

    if(current == root) {
        root = null;
        return;
    }
    //Case 1: If node to be removed is a leaf, no children.
    if(current.getLeftNode() == null && current.getRightNode() == null) {
        if(isLeftNode)
            parent.setLeftNode(null);
        else
            parent.setRightNode(null);
    }
    //Case 2: If node to be removed has only 1 child.
    else if(current.getLeftNode() != null && current.getRightNode() == null) {
        if(isLeftNode)
            parent.setLeftNode(current.getLeftNode());
        else
            parent.setRightNode(current.getLeftNode());
    }
    else if(current.getLeftNode() == null && current.getRightNode() != null) {
        if(isLeftNode)
            parent.setLeftNode(current.getRightNode());
        else
            parent.setRightNode(current.getRightNode());
    }
    //Case 3: If node to be deleted has 2 children.
    else {
        Node smallest = findSmallest(current.getRightNode());
        current.setData(smallest.getData());
        //Calling recursion to delete the smallest. Because the smallest
        //might have a right subtree. Explanation above relates to this.
        delete(current.getRightNode(), smallest.getData());
        //Calling the delete method to start deleting from the right sub
        //tree since at this point there is a duplicate value, I can't
        //start from the root.
    }
}

public Node findSmallest(Node start) {
    //This is so in the main method, I can call findSmallest and pass in
    //null to search the whole tree. Because in main, I won't have reference
    //to the root. I have the start parameter so I can specifiy where to
    //start the search, because of the way I am dealing with deleting
    //a node with 2 children. See above.
    Node smallest = start == null ? root : start;

    while(smallest.getLeftNode() != null) {
        smallest = smallest.getLeftNode();
    }
    return smallest;
}
\$\endgroup\$
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Sep 2 '18 at 12:36
2
\$\begingroup\$
public Node findSmallest(Node start) {
    //This is so in the main method, I can call findSmallest and pass in
    //null to search the whole tree. Because in main, I won't have reference
    //to the root. I have the start parameter so I can specifiy where to
    //start the search, because of the way I am dealing with deleting
    //a node with 2 children. See above.
    Node smallest = start == null ? root : start;

    while(smallest.getLeftNode() != null) {
        smallest = smallest.getLeftNode();
    }
    return smallest;
}

I would break this into two methods:

public Node findSmallest() {
    return findSmallest(root);
}

private Node findSmallest(Node candidate) {
    // I have the start parameter so I can specify where to
    // start the search, because of the way I am dealing with deleting
    // a node with 2 children. See above.
    while (candidate.getLeftNode != null) {
        candidate = candidate.getLeftNode();
    }

    return candidate;
}

Now your external caller isn't asked to pass information that it doesn't have. And you don't have to check whether the method is being called internally or externally on every call.

I prefer the name candidate to smallest for accuracy's sake. Until the last iteration, it's not the smallest. It's a candidate to be the smallest on every iteration.

    }
    //Case 3: If node to be deleted has 2 children.
    else {

I'm not a fan of the half-cuddled else in the first place, but if you have to use it, please use it without separation. It's bad enough that C-style languages (e.g. Java) do not explicitly end their if/then blocks. Adding arbitrary content between the then block and the else just makes this worse.

    }
    else {
        // Case 3: If node to be deleted has 2 children.

Now I can easily see that there is an else. I don't have to scroll down to the next statement to see if it might be an else.

Also, there are four cases, not three. Your case 2 is two cases: a null left child or a null right.

    while(data != current.getData() && current != null) {

This is a bug. Create a test case where the data is not found and you'll see.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your reply. I have added a new version of the delete method, could you look at that? I implemented this yesterday, and I like it much better than the first implementation. I took into account about splitting the method, that is a nice way of dealing with it. \$\endgroup\$ – Rino Leonardino Sep 2 '18 at 11:42
0
\$\begingroup\$

I have implemented a new way of the delete method, I took some of the suggestions that @mdfst13 suggested, and I am pretty happy about it, but would really like some feedback on it.

New code:

public void delete(int data) {
    delete(root, root, data);
}

private void delete(Node parent, Node current, int data) {

    if(current == null) return;

    if(data < current.getData())
        delete(current, current.getLeftNode(), data);
    else if(data > current.getData())
        delete(current, current.getRightNode(), data);
    else { //found, current is equal to the node to be deleted.

        boolean isLeft = true;
        //Here I am checking to see which of the left and right references
        //I need to update for the parent, for case 1 and 2.
        if(parent.getLeftNode().getData() == current.getData()) isLeft = true;
        else isLeft = false;

        //Case 1: If node to be removed is a leaf, no children.
        if(current.getLeftNode() == null && current.getRightNode() == null) {
            if(isLeft) parent.setLeftNode(null);
            else //Meaning the node to be deleted is the right node of the parent.
                parent.setRightNode(null);
        }
        //Case 2: If node to be removed has 1 child.
        else if(current.getLeftNode() != null && current.getRightNode() == null) {
            if(isLeft) parent.setLeftNode(current.getLeftNode());
            else parent.setRightNode(current.getLeftNode());
        }
        else if(current.getRightNode() != null && current.getLeftNode() == null) {
            if(isLeft) parent.setLeftNode(current.getRightNode());
            else parent.setRightNode(current.getRightNode());
        }
        else {
            //Case 3: If node to be deleted has 2 children.
            Node smallest = findSmallest(current.getRightNode());
            current.setData(smallest.getData());
            delete(current, current.getRightNode(), smallest.getData());
        }
    }
}

public Node findSmallest() {
    return findSmallest(root);
}

private Node findSmallest(Node start) {

    Node smallest = start;

    while(smallest.getLeftNode() != null) {
        smallest = smallest.getLeftNode();
    }
    return smallest;
}
\$\endgroup\$
  • \$\begingroup\$ If you are looking for feedback, you should post a new question that links back to this question. Under the link that @Mast posted, the critical words are Posting a new question. A self-answer is to share what you learned with others and should include an explanation of why you made the decisions that you did. \$\endgroup\$ – mdfst13 Sep 2 '18 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.