Course contentsShow
← Computer Science
Lesson 509 of 2,87212. Binary Search TreesFree lesson

BST Deletion: One Child Case

Delete a node with one child by replacing it with its only child, bypassing the deleted node.

BST Deletion: One Child Case

What You'll Learn

You'll learn how to delete a node from a Binary Search Tree when that node has exactly one child by promoting its child to take its place.

The Core Idea

When you need to delete a node that has only one child (either a left child or a right child, but not both), the solution is elegantly simple: bypass the node by connecting its parent directly to its only child.

Think of it like removing a link in a chain. If someone in the middle of a human chain drops out, the person before them simply grabs the hand of the person after them. The chain remains unbroken, just one person shorter.

How It Works

When deleting a node with one child:

  1. Identify the child: Determine whether the node has a left child or right child
  2. Preserve the subtree: That child represents an entire subtree that must remain in the tree
  3. Reconnect: Link the deleted node's parent directly to this child
  4. Maintain BST property: Since the child was already in the correct BST position (smaller than ancestors if on the left, larger if on the right), the invariant is preserved

The beauty of this case is that the BST ordering remains valid. The single child and its entire subtree were already correctly positioned relative to the rest of the tree, so simply promoting them one level up doesn't violate any BST rules.

Why This Works

The node you're deleting sits between its parent and its child. Both relationships already satisfy the BST property. Removing the middle node and connecting parent to child directly maintains those ordering relationships perfectly.

Key Takeaway: Deleting a BST node with one child requires simply bypassing it—connect the parent to the node's only child, preserving both the tree structure and the BST ordering property.