Deleting a node from a binary search tree

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

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

    ahh @codesparkle, this is just a pesudo code, I am sorry not being specific

    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...

    sure, would like to see the version

    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.

    correctness of program is what I am interested in :). thnks for your edit

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

    I think it would be good if `Node` class doesn't have a `Node`, rather make a `Tree` class which contains `Node`s.

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

    This is not a suggestion on how to improve the code in question.

    @svick, isn't it? It's poorly written yes, but it is trying to point a bug I think.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM