Other Versions

http://www.cplusplus.happycodings.com/Algorithms/code5.html

```void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;

if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
tree_node* curr;
tree_node* parent;

//first we do look up
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d > curr->data)
curr = curr->right;
else
curr = curr->left;
}
}

if(!found)
{
return;
}

// There are 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children

//We're looking at a leaf node, just assign parent's left or right=NULL, delete node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr)
parent->left = NULL;
else
parent->right = NULL;
delete curr;
return;
}

// Node with single child,  just assign parent's left or right= node's single child, delete node
if((curr->left == NULL && curr->right != NULL) ||
(curr->left != NULL  && curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}

//Node with 2 children, replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;

//if the node's right child has a left child
// Move all the way down left to locate smallest element

if(chkr ->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;

lcurr = chkr ->left;
lcurrp = chkr ;

while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}

curr->data = lcurr->data;
lcurrp->left = lcurr->right;

delete lcurr;

}
else
{
//swap curr data with right node, and assign right's right child.

curr->data = chkr ->data;
curr->right = chkr ->right;

delete chkr;
}
return;
}

}
```

http://en.wikipedia.org/wiki/Binary_search_tree#Deletion

``````def spliceOut(self,parent):
if (! self.leftChild && ! self.rightChild):
if self == parent.leftChild:
parent.leftChild = None
else:
parent.rightChild = None

return self;

elif ( (self.leftChild && ! self.rightChild) || (!self.leftChild && self.rightChild) )
if self.leftChild:
if self == parent.leftChild:
parent.leftChild = self.leftChild
else:
parent.rightChild = self.leftChild
else:
if self == parent.leftChild:
parent.leftChild = self.rightChild
else:
parent.rightChild = self.rightChild

return self;

else :
not doable;

def binary_tree_delete(self, key):
if self.key == key:
if(self has only one child)
self.spliceOut()
delete self

/*        if (! self.leftChild && ! self.rightChild):
if self == self.parent.leftChild:
self.parent.leftChild = None
else:
self.parent.rightChild = None

delete self

elif  ( (self.leftChild && ! self.rightChild) || (!self.leftChild && self.rightChild) )
if self.leftChild:
if self == parent.leftChild:
parent.leftChild = self.leftChild
else:
parent.rightChild = self.leftChild
else:
if self == parent.leftChild:
parent.leftChild = self.rightChild
else:
parent.rightChild = self.rightchild

delete self
*/
else:
succ = self.findSuccessor()
succ.spliceOut()

self.data = succ.data
delete succ;
/*
or
succ.leftChild = self.leftChild
succ.rightChild = self.rightChild

if self == parent.leftChild:
parent.leftChild = succ
else:
parent.rightChild = succ

delete self
*/```
```