# Deleting a node from Binary Search Tree

I have read about it at few places and tried to write my own version, 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())); –  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
show 1 more comment

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
*/
{
//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
*/
{
}

/**
* 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
*/
{

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

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)
{
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
{
node = new Node<Integer>(1);
assertTrue(node.getValue() == 1);
assertTrue(node.getLeft() == null);
assertTrue(node.getRight() == null);

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

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

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

@Test
public void testCorrectness()
{
assertTrue(delBst.getNumberOfNodes() == 6);

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

@Test
public void testDeleteNode()
{
/*
* 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);
}
}

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