#Does this function handle all cases of deleting a node from the BST?

1 messages · Page 1 of 1 (latest)

lucid forumBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

# 
void deletion(node** root, int value) {
  node *p = *root, *q = *root;
  while ((p) && (p->value != value)) {
    q = p;
    if (value > p->value)
      p = p->right;
    else
      p = p->left;
  }
  if (!p)
    return;
  if (p->left == NULL) {
    if ((*root)->value != p->value) {
      if (q->left == p)
        q->left = p->right;
      else
        q->right = p->right;
    } else
      (*root)->right = p->right;
    free(p);
  } else if (p->right == NULL) {
    if ((*root)->value != value) {
      if (q->left == p)
        q->left = p->left;
      else
        q->right = p->left;
    } else
      (*root)->left = p->left;
    free(p);
  } else {
    node *g = p, *d;
    d = g;
    g = g->left;
    while (g->right) {
      d = g;
      g = g->right;
    }
    d->right = NULL;
    p->value = g->value;
    free(g);
  }
}
# 
void deletion(node** root, int value) {
  node *p = *root, *q = *root;
  while ((p) && (p->value != value)) {
    q = p;
    if (value > p->value)
      p = p->right;
    else
      p = p->left;
  }
  if (!p)
    return;
  if (p->left == NULL) {
    if ((*root)->value != p->value) {
      if (q->left == p)
        q->left = p->right;
      else
        q->right = p->right;
    } else
      (*root)->right = p->right;
    free(p);
  } else if (p->right == NULL) {
    if ((*root)->value != value) {
      if (q->left == p)
        q->left = p->left;
      else
        q->right = p->left;
    } else
      (*root)->left = p->left;
    free(p);
  } else {
    node *g = p, *d;
    d = g;
    g = g->left;
    while (g->right) {
      d = g;
      g = g->right;
    }
    if (d != g)
      d->right = NULL;
    else
      p->right = g->left;
    p->value = g->value;
    free(g);
  }
}
lucid forumBOT
#

@idle mango

Please Do Not Delete Posts!

Please don't delete forum posts. They can be helpful to refer to later and other members can learn from them. In the future you can use !solved to close a post and mark a post as solved.

idle mango
#

!solve