Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have read about it at a few places and tried to write my own version. I would like to get it reviewed.

class Node {
    private int value;
    private Node left;
    private Node right

    // getters and setters
}

public class DeleteNodeBST {

    Node parent = null;

    boolean deleteNodeBST(Node node, int value) {
        if (node == null) {
            return false;
        }
        if (node.getValue() == value) {

            if ((node.getLeft() == null) && (node.getRight() == null)) {
                // leaf node
                node = null;
                return true;
            }

            if ((node.getLeft() != null) && (node.getRight() != null)) {
                // node with two children
                node.setValue(findMinimumAndReturnWithDelete(node.getRight()));
                return true;
            }

            // either left child or right child
            if (node.getLeft() != null) {
                parent.setLeft(node.getLeft());
                node = null;
                return true;
            }

            if (node.getRight() != null) {
                parent.setRight(node.getRight());
                node = null;
                return true;
            }
        }
        parent = node;
        if (node.getValue() > value) {
            return deleteNodeBST(node.getLeft(), value);
        } else {
            return deleteNodeBST(node.getRight(), value);
        }
    }

    int findMinimumAndReturnWithDelete(Node node) {
        if (node.getLeft() == null) {
            int v = node.getValue();
            node = null;
            return v;
        }
        return findMinimumAndReturnWithDelete(node.getLeft());
    }
}
share|improve this question
1  
there are compile errors... missing a semicolon ; after right... missing a return type (boolean) before deleteNodeBST(Node node, int value)... node == null; is a condition so it can't be used as a statement, did you mean node = null;? and the last line has to be return findMinimumAndReturnWithDelete(node.getLeft()); because all code paths have to return a value. And what the hell is node.setValue() = findMinimumAndReturnWithDelete(node.getRight());? you're assigning a value to a method? surely you meant node.setValue(findMinimumAndReturnWithDelete(node.getRight())); –  codesparkle Jul 2 '12 at 21:00
    
ahh @codesparkle, this is just a pesudo code, I am sorry not being specific –  daydreamer Jul 2 '12 at 21:12
    
the faq requires real code as opposed to pseudo-code. And even as pseudo-code, leaving out the returns makes no sense. If you like I'll paste in a compiling version of your code... –  codesparkle Jul 2 '12 at 21:14
    
sure, would like to see the version –  daydreamer Jul 2 '12 at 21:14
    
I've proposed an edit, but that still needs to be accepted by a mod. Note that though this satisfies the compiler, I by no means have any idea whether it actually runs properly. –  codesparkle Jul 2 '12 at 21:19

2 Answers 2

Here is how I would do this. I've sprinkled comments throughout the code, so hopefully this will be helpful.

//generalize the node to work for types other than just int
public class Node<T extends Comparable<? super T> >
{
    private T value; //get; set;
    private Node<T> left; //get; set;
    private Node<T> right; //get; set;

    /**
     * construct a Node with value
     *
     * @param val value for this node
     */
    public Node(T val)
    {
        value = val;
        left = null;
        right = null;
    }

    /**
     * copy constructor
     * 
     * @param n node to copy from
     */
    public Node(Node<T> n)
    {
        value = n.value;
        left = n.left;
        right = n.right;
    }

    /**
     * @return true if this node has no children
     */
    public boolean isLeaf()
    {
        return (left == null && right == null);
    }

    public Node<T> getLeft() { return left; }
    public Node<T> getRight() { return right; }
    public T getValue() { return value; }
    public void setLeft(Node<T> n) { left = n; }
    public void setRight(Node<T> n) { right = n; }
    public void setValue(T v) { value = v; }
}

And the BST. Since it doesn't really make sense to delete without being able to add nodes to the tree first, I've put in adding as well.

public class DeleteNodeBST<T extends Comparable<? super T> >
{
    private Node<T> root = null;
    private int nodes = 0; //get;

    /**
    * add a node to the tree
    *
    * @param n node to add
    * @return true if add is successful
    */
    public boolean add(final Node<T> n)
    {
        //null guard
        if (n == null || n.getValue() == null)
        {
            return false;
        }

        boolean isSuccessful;
        if (root == null)
        {
            root = n;
            ++nodes;
            isSuccessful = true;
        }
        else
        {
            isSuccessful = findHome(root, n);
        }

        return isSuccessful;
    }

    /**
     * create a node containing input value and add it to the tree
     * 
     * @param val value for new node
     * @return true if add is successful
     */
    public boolean add(final T val)
    {
        return add( new Node<T>(val) );
    }

    /**
     * attempt to place a node under another
     * 
     * @param adoptor node to look under
     * @param adoptee child node looking for a home
     * @return true if child node finds a place, otherwise false
     */
    private boolean findHome(Node<T> adoptor, final Node<T> adoptee)
    {
        int comp = adoptor.getValue().compareTo( adoptee.getValue() );

        if (comp > 0)   //adoptor comps greater than adoptee, so go left
        {
            if (adoptor.getLeft() == null)
            {
                adoptor.setLeft(adoptee);
                ++nodes;
                return true;
            }
            //recurse until we find somewhere to place the adoptee node
            return findHome(adoptor.getLeft(), adoptee);
        }
        else if (comp < 0)  //adoptor comps less than adoptee, so go right
        {
            if (adoptor.getRight() == null)
            {
                adoptor.setRight(adoptee);
                ++nodes;
                return true;
            }
            //recurse until we find somewhere to place the adoptee node
            return findHome(adoptor.getRight(), adoptee);
        }

        return false;
    }

    /**
     * attempts to delete a node from the tree
     * 
     * @param n node to delete
     * @return true if node is deleted, otherwise false
     */
    public boolean delete(Node<T> n)
    {
        //null guard
        if (n == null || n.getValue() == null)
        {
            return false;
        }

        return delete( n.getValue() );
    }

    /**
     * attempts to delete a node from the tree containing the value
     * 
     * @param val value of node to delete
     * @return true if node is deleted, otherwise false
     */
    public boolean delete(final T val)
    {
        //the node to be deleted
        Node<T> target = null;
        //to keep track of parent node
        Node<T> parent = null;
        //variable node reference
        Node<T> node = root;

        while (node != null)
        {
            if (val.compareTo( node.getValue() ) == 0)  //eureka!
            {
                target = node;
                break;
            }
            else if (val.compareTo( node.getValue() ) > 0)  //target greater, so go right
            {
                parent = node;
                node = node.getRight();
            }
            else    //target less, so go left
            {
                parent = node;
                node = node.getLeft();
            }
        }

        if (target == null)
        {
            //target not found
            return false;
        }

        boolean isLeft = (target == parent.getLeft() );

        if (target == root) //the node that's baleeting is in fact the root node
        {
            //get last house on the left on the right!
            //it becomes the new root
            node = getLastHouseOnTheLeft( parent.getRight() );
            if (node != null)
            {
                node.setLeft( parent.getLeft() );
                node.setRight( parent.getRight() );
                root = node;
            }
        }
        else if ( target.isLeaf() )
        {
            if (isLeft)
            {
                parent.setLeft(null);
            }
            else
            {
                parent.setRight(null);
            }
        }
        else if (target.getLeft() != null && target.getRight() != null) //two children, some shuffling
        {
            if (isLeft)
            {
                parent.setLeft( target.getRight() );
                parent.getLeft().setLeft( target.getLeft() );
            }
            else
            {
                parent.setRight( target.getRight() );
                parent.getRight().setLeft( target.getLeft() );
            }
        }
        else    //one child is simpler
        {
            if (target.getLeft() == null)
            {
                if (isLeft)
                {
                    parent.setLeft( target.getLeft() );
                }
                else
                {
                    parent.setRight( target.getLeft() );
                }
            }
            else
            {
                if (isLeft)
                {
                    parent.setLeft( target.getRight() );
                }
                else
                {
                    parent.setRight( target.getRight() );
                }
            }
        }

        return true;    //baleeted
    }

    /**
     * extract the last house on the left
     * 
     * @param start the node to start on
     * @return the last house on the left
     */
    private Node<T> getLastHouseOnTheLeft(final Node<T> start)
    {
        Node<T> candidate = null;
        Node<T> parent = null;
        Node<T> node = start;

        while (node != null)
        {
            if ( node.getLeft() != null )
            {
                parent = node;
                candidate = node.getLeft();
            }

            node = node.getLeft();
        }

        if (parent != null)
        {
            parent.setLeft(null);
        }

        return candidate;
    }

    /**
     * get a node from the value it's associated with
     * 
     * @param v value as a key to finding the node containing it
     * @return node associated with the value
     */
    public Node<T> getNode(T v)
    {
        //null guard
        if (v == null)
        {
            return null;
        }

        Node<T> node = root;
        int comp;
        while (root != null)
        {
            comp = node.getValue().compareTo(v);
            if (comp == 0)
            {
                return node;
            }
            if (comp > 0)
            {
                node = node.getLeft();
            }
            else
            {
                node = node.getRight();
            }
        }

        return node;
    }

Finally, some simple test cases, plus an example graph:

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class TestDeleteNodeBST
{
    DeleteNodeBST<Integer> delBst;
    Node<Integer> node;

    @Before
    public void init()
    {
        delBst = new DeleteNodeBST<Integer>();

        assertTrue(delBst.getNumberOfNodes() == 0);
    }

    @Test
    public void testAddNode()
    {
        node = new Node<Integer>(1);
        assertTrue(node.getValue() == 1);
        assertTrue(node.getLeft() == null);
        assertTrue(node.getRight() == null);

        delBst.add(node);
        assertTrue(delBst.getNumberOfNodes() == 1);

        Integer two = 2;
        assertTrue( two > node.getValue() );
        assertTrue( two.compareTo(node.getValue() ) > 0 );

        delBst.add(two);
        assertTrue(delBst.getNumberOfNodes() == 2);
        assertTrue( delBst.getNode(2).getValue().equals(2) );
    }

    @Test
    public void testCorrectness()
    {
        delBst.add(5);
        delBst.add(4);
        delBst.add(3);
        delBst.add(2);
        delBst.add(1);
        delBst.add(0);
        assertTrue(delBst.getNumberOfNodes() == 6);

        node = delBst.getNode(3);
        assertTrue(node.getValue() == 3);
    }

    @Test
    public void testDeleteNode()
    {
        delBst.add(5);
        delBst.add(4);
        delBst.add(6);
        delBst.add(7);
        delBst.add(2);
        delBst.add(3);
        delBst.add(1);
        /*
         * tree should look like this now
         *           5
         *        4     6
         *      2         7
         *     1 3
         */
        assertTrue( delBst.delete(2) ); //3 should take 2's place
        assertFalse( delBst.delete(2) );//nothing to delete now
        node = delBst.getNode(3);
        assertTrue(node.getValue() == 3);
        assertTrue(node.getRight() == null);
        assertTrue(node.getLeft().getValue() == 1);
    }
}
share|improve this answer
1  
+1 So much effort! –  Alain Jul 6 '12 at 15:00
    
I think it would be good if Node class doesn't have a Node, rather make a Tree class which contains Nodes. –  tintinmj Jul 24 '13 at 17:04

I discovered a bug: your code failed when I tried to delete the node for the root (value=5). In the delete function, the parent.getLeft() method causes a NullPointerException since parent is null. This is the offending line:

boolean isLeft = (target == parent.getLeft());
share|improve this answer
    
This is not a suggestion on how to improve the code in question. –  svick Apr 22 '13 at 18:50
1  
@svick, isn't it? It's poorly written yes, but it is trying to point a bug I think. –  Winston Ewert Apr 23 '13 at 2:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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