Deleting a node from a binary search tree

Question

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

Answer 1

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

Answer 2

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());