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

• Adam: 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()))
• daydreamer: ahh @codesparkle, this is just a pesudo code, I am sorry not being specific
• Adam: 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...
• daydreamer: sure, would like to see the version
• Adam: 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.

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

• Anirban Nag 'tintinmj': I think it would be good if Node class doesn't have a Node, rather make a Tree class which contains Nodes.

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

• svick: This is not a suggestion on how to improve the code in question.
• Winston Ewert: @svick, isn't it? It's poorly written yes, but it is trying to point a bug I think.