C in 100 Seconds: Binary Search Tree

Binary Search Tree — Search and Delete

A binary search tree keeps values sorted — smaller goes left, larger goes right. Searching means going left or right at each node until you find what you want or hit NULL.

Search

Node *search(Node *root, int value) {
  if (root == NULL || root->data == value) return root;
  if (value < root->data) return search(root->left, value);
  return search(root->right, value);
}

If the value is less than the current node, go left. Otherwise go right. Each step eliminates half the remaining tree.

Delete — Three Cases

Deleting from a BST depends on how many children the target node has.

Case 1: Leaf node (no children)

if (root->left == NULL && root->right == NULL) {
  free(root);
  return NULL;
}

Just free it and return NULL.

Case 2: One child

if (root->left == NULL) {
  Node *temp = root->right;
  free(root);
  return temp;
}

Replace the node with its only child.

Case 3: Two children

Node *min = find_min(root->right);
root->data = min->data;
root->right = delete(root->right, min->data);

Find the inorder successor (smallest node in the right subtree), copy its value, then delete the successor.

Output

Tree: 20 30 40 50 60 70
Search 40: found
Search 99: not found

Delete 20 (leaf): 30 40 50 60 70
Delete 30 (one child): 40 50 60 70
Delete 50 (two children): 40 60 70

Each delete case handled correctly. The inorder traversal confirms the BST property is maintained after every deletion.