binary tree remove func

[nhrnjic6]

This is the function :

node* remove (node* p_tree, int key)
{
if ( p_tree == NULL )
{
return NULL;
}
if ( p_tree->key_value == key )
{
// the first two cases handle having zero or one child node
if ( p_tree->p_left == NULL )
{
node* p_right_subtree = p_tree->p_right;
delete p_tree;
// this might return NULL if there are zero child nodes,
// but that is what we want anyway
return p_right_subtree;
}
if ( p_tree->p_right == NULL )
{
node* p_left_subtree = p_tree->p_left;
delete p_tree;
// this will always return a valid node, since we know
// is not NULL from the previous if statement
return p_left_subtree;
}

node* p_max_node = find_max( p_tree->p_left );
p_max_node->p_left = p_tree->p_left;  // equal to what??
p_max_node->p_right = treep_->p_right; // equal to what??
delete p_tree;
return p_max_node;


so the find_goes until it hits last element on the right side, meaning that element is the bigest so it can replace       removing element. If the removing element was 25, and it had 2 children (L 15, R 30), is that what these 2 statements are equal to ?? 

[rubberman]

Go read Donald Knuth's "The Art of Computer Programming" Volume 3 - Sorting and searching. He gets into this in quite a bit of detail. In fact, this is considered the "Bible" of the subject, especially binary tree algorithms. It has held an honored central location on my 6' x 12' (six by twelve feet - 72 sq feet) office bookshelf for many, many years.