Thread: deleting a node in a recursive way algorithm..

after solving the previus one with the root.
i looked in
Eternally Confuzzled - Binary Search Trees I
but i coudnt see the general algorithm for
deleting a node in a BST tree in a recursive way
so it will remain BST afterward

?

If you delete a node in a binary search tree the data structure is still a binary search tree. The tree would be rebalanced when you insert something again. At least, that's my understanding.

i have some corrections to the original question:
the node to be deleted is not te root
it has only one son or no sons.

regarding whiteflags post:
if i free the wanted node i need to rearrange the tree in order to make it BST
i have been given in a previous article to help
but i cant see there a way of solving this one.

Code:

p
  \
  d
/  \
*  *

p
 \
 d
/ \
c  *

If d has a child:
d and c swap
separate d from tree, replace with empty leaf
free d

If d is childless:
separate d from tree
replace d with empty leaf
free d

It's not much more than that and in fact it's one of the first things it covers regarding deletion. Like I said it's still a tree.

are you sure that avl is my answer
because i am ask to act on pure BST
not self balancing bst trees

correct me if i am wrong
balanced means that height of the left subtree minus height of the right tree
is less then two.

so thats not what i am looking for

so i will use whiteflags method:

"If d has a child:
d and c swap
separate d from tree, replace with empty leaf
free d"
you didnt tell what node are you deleting.
i didnt see what node dissapears in the tree

??

Code:

template <typename ElemType>
bool BST<ElemType>::remove(ElemType data) {
     return recRemoveNode(root, data);
}
template <typename ElemType>
bool BST<ElemType>::recRemoveNode(nodeT *& t, ElemType data) {
  if (t == NULL) return false;
  int sign = cmpFn(data, t->data);
  if (sign == 0) {
    removeTargetNode(t);
    return true;
    } else if (sign < 0) {
    return recRemoveNode(t->left, data);
    } else {
    return recRemoveNode(t->right, data);
  }
}

i think its a c++ code i am not familiar with it.(i am taking a basic C course)
what is

i would like to understand the algorithm and to write the code my self.

suppose i will find the node i want to delete

there is a surrounding connections
(the node to be deleted is not the root it has only one son or no sons.)
so i will have to keep the father of the to be deleted node.
and then reconnect the father with one of it sons

correct?