How to delete a node from Binary Search Tree. - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# How to delete a node from Binary Search Tree.

Posts: 22Member
[b][red]This message was edited by ss1289 at 2005-12-1 20:53:16[/red][/b][hr]
[b][red]This message was edited by ss1289 at 2005-12-1 18:6:58[/red][/b][hr]
[b][red]This message was edited by ss1289 at 2005-12-1 18:6:23[/red][/b][hr]
I can't figure this out.
I'm trying to delete the odd numbered nodes from a BST and I'm having a hard time understanding it.
Here is what I have,
modify 1 = do nothing
modify 2 = insert
modify 3 = delete
Im having a problem when modify = 3..

[code]bool BST::findit(node * & ptr, const T & x, int modify)
{
if(ptr == 0)
{
if(modify == 0)
return false;

if(modify == 1)
{
ptr = new node;
ptr->data = x;
return false;
}

if(modify == 2)
return false;

return false;
}

if(ptr->data == x)
{
if(modify == 0)
return true;

if(modify == 1)
return true;

if(modify == 2)
{
node *prev, *temp = ptr;
if(ptr -> right == 0)
ptr = ptr->left;
else
if(ptr -> left == 0)
ptr = ptr -> right;
if(ptr->left != 0 && ptr->right != 0)
{
temp = ptr -> left;
prev = ptr;
while (temp -> right != 0)
{
prev = temp;
temp = temp -> right;
}
ptr->data = temp->data;
if(prev == ptr)
prev -> left = temp -> left;
else prev -> right = temp -> left;
}
delete temp;
return true;
}
}

if(ptr->data < x)
return findit(ptr->right, x, modify);
else
return findit(ptr->left, x, modify);

}[/code]