Problem with pointers in binary search tree deletion.

Question

I am trying to implement binary search tree operations and got stuck at deletion.

  11
 /  \
10  14 

Using inorder traversal as representation of tree initially output is 10 11 14.

Deleting node 10, output expected is 11 14 but I am getting 0 11 14.

Deleting node 14, output expected is just 11 but I am getting 0 11 67837.

Please explain why I am getting wrong output. I am not looking for any code :).

typedef struct _node{
  int data;
  struct _node *left;
  struct _node *right;
} Node;

Node* bstree_search(Node *root, int key)
{
  if(root == NULL){
    return root;
  }
  // Based on binary search relation, key can be found in either left,
  // right, or root.
  if(key > root->data)
    return bstree_search(root->right, key);
  else if(key < root->data)
    return bstree_search(root->left, key);
  else
    return root;
}
void bstree_insert(Node **adroot, int value)
{
  // since address of address(root is itself address) is passed we can change root.
  if(*adroot == NULL){
    *adroot = malloc(sizeof(**adroot));
    (*adroot)->data = value;
    (*adroot)->right = (*adroot)->left = NULL;
    return;
  }
  if(value > (*adroot)->data)
    bstree_insert(&(*adroot)->right, value);
  else
    bstree_insert(&(*adroot)->left, value);
}

void bstree_inorder_walk(Node *root)
{
  if(root != NULL){
    bstree_inorder_walk(root->left);
    printf("%d ",root->data);
    bstree_inorder_walk(root->right);
  }
}
void bstree_delete(Node **adnode)
{
  //Node with no children or only one child
  Node *node, *temp;
  node = temp = *adnode;
  if((*adnode)->right == NULL || (*adnode)->left == NULL){
    if((*adnode)->right == NULL){
      *adnode = (*adnode)->left;
    }else{
      *adnode = (*adnode)->right;
    }
  }else{ // Node with two children

  }
  free(temp);
}

int main()
{
  Node *root = NULL;
  Node *needle = NULL;
  int i,elems[] = {11,10,14};

  for(i = 0; i < 3; ++i)
    bstree_insert(&root,elems[i]);

  bstree_inorder_walk(root);
  printf("\n");

  needle = bstree_search(root, 10);
  bstree_delete(&needle);
  bstree_inorder_walk(root);
  printf("\n");

  needle = bstree_search(root, 14);
  bstree_delete(&needle);
  bstree_inorder_walk(root);
  printf("\n");
}

Answer 1

Please explain why I am getting wrong output.

Your delete function must also change the parent of the deleted Node. For example, when you delete the node holding 10, you must set the root Node's left child to NULL. Since you don't do this, when you later traverse the tree, you print out data that has already been freed.

I did not look at any code other than delete, so I can't make any guarantees about it working once this change is made.

Answer 2

You're getting wrong output because your deletion code is buggy (okay, maybe that's stating the obvious).

To delete from a binary search tree, you first find the node to be deleted. If it's a leaf node, you set the pointer to it in its parent node to NULL, and free the node. If it's not a leaf node, you take one of two leaf nodes (either the left-most child in the right sub-tree, or the right-most child in the left sub-tree) and insert that in place of the node you need to delete, set the pointer to that node in its previous parent to NULL, and delete the node you've now "spliced out" of the tree.

Answer 3

A couple of things really quick,

first when you allocate the node, you really should be doing the malloc on the sizeof the type (ie Node).

Second, if you have 2 children it looks like you are not really deleting the node and rebuilding the search tree by promoting one of the children.

Other people have already got you other obvious errors.