A binary search tree, or BST, is a binary tree that follows a specific ordering rule to make values easier to find. Each node can have up to two children—a left child and a right child—and the tree maintains the following property:
If a node contains the value X:
-
Every value in its left subtree is less than
X. -
Every value in its right subtree is greater than
X.
At first, a binary search tree can feel like a tree that somehow keeps itself sorted. Like a sorted array, it maintains values in order, but it also lets us find a value by repeatedly comparing it with the current node and choosing which direction to go.
For beginners, searching and insertion are usually straightforward. Deletion is where things tend to become confusing. In this article, we will look at how binary search trees work, with particular attention to understanding BST deletion in an intuitive way.
What Is a Binary Search Tree?
A BST can be summarized in one sentence:
A binary search tree is a binary tree that follows an ordering rule.
For every node with a value X, the left subtree contains only values smaller than X, while the right subtree contains only values greater than X. This rule applies recursively throughout the entire tree.
Once you remember this rule, nearly every BST operation begins to follow the same pattern:
- Compare the target value with the current node.
- Move either left or right.
- Repeat until the operation is complete.
That is the basic idea behind searching, insertion, and even deletion.
Searching a Binary Search Tree
Searching is the most intuitive BST operation.
Start at the root and compare the target value with the value of the current node:
- If the values are equal, the target has been found.
- If the target is smaller, move to the left child.
- If the target is larger, move to the right child.
-
If you reach an empty position (
None), the value is not in the tree.
The important point is that you do not need to search both sides at every step. The ordering rule tells you which single direction to follow.
If the tree is reasonably balanced, the number of steps is approximately proportional to log n, so searching is efficient. However, if the tree becomes heavily skewed to one side, the number of steps may approach n. In that case, the BST starts to behave more like a linked list.
This is an important characteristic of binary search trees: they perform well when their structure remains balanced, but their performance can deteriorate significantly when the tree becomes skewed.
class Node: def __init__(self, val): self.val = val self.left: "Node | None" = None self.right: "Node | None" = None def bst_search(root: Node | None, key: int) -> Node | None: """ Iterative BST search - key == current value: target found - key < current value: move left - key > current value: move right - None reached: target is not in the tree """ cur = root while cur is not None: if key == cur.val: return cur elif key < cur.val: cur = cur.left else: cur = cur.right return None # -------------------- Build an example tree -------------------- # 10 # / \ # 5 15 # / \ / \ # 2 7 12 20 root = Node(10) root.left = Node(5) root.right = Node(15) root.left.left = Node(2) root.left.right = Node(7) root.right.left = Node(12) root.right.right = Node(20) # -------------------- Test the search function -------------------- for k in [7, 12, 9, 20, 1]: found = bst_search(root, k) if found: print(f"Found: {k} (node value = {found.val})") else: print(f"Not found: {k}")
Inserting a Value into a BST
Insertion works almost exactly like searching.
To insert a new value, start at the root and compare the new value with the current node. Continue moving left or right until you reach an empty position. The new node is then attached at that position.
A useful way to think about insertion is:
Insertion is a search that places a new node at the first available position.
How duplicate values are handled depends on the implementation. When first learning about BSTs, it is usually easiest to assume that duplicate values are not allowed. If a duplicate is found, the function simply leaves the tree unchanged.
If duplicates must be supported, you need a clear policy. For example, each node could store a count, or duplicate values could always be placed on a particular side. These policies are useful in real applications, but they can distract from the main BST concept when you are just getting started.
class Node: def __init__(self, val): self.val = val self.left: "Node | None" = None self.right: "Node | None" = None def bst_insert(root: Node | None, key: int) -> Node: """ Iterative BST insertion Duplicate policy: If the key already exists, do not insert another node. The function always returns the root because the original tree may be empty. """ # Create a new root if the tree is empty if root is None: return Node(key) cur = root while True: if key == cur.val: # Duplicate found: leave the tree unchanged return root elif key < cur.val: if cur.left is None: cur.left = Node(key) return root cur = cur.left else: if cur.right is None: cur.right = Node(key) return root cur = cur.right # -------------------- Example -------------------- # Initial tree: 10 as the root, with 5 and 15 as its children root = Node(10) root.left = Node(5) root.right = Node(15) # Insert values, including duplicates for k in [7, 12, 5, 2, 20, 10]: root = bst_insert(root, k) # Use an inorder traversal to check the result. # A valid BST produces values in ascending order. def inorder(node: Node | None): if not node: return inorder(node.left) print(node.val, end=" ") inorder(node.right) inorder(root) # Expected output: 2 5 7 10 12 15 20 print()
Deleting a Node from a BST
Deletion is the operation that usually causes the most confusion.
A helpful way to understand it is:
Deleting a BST node is not simply about removing it. It is about deciding what should take its place.
Instead of thinking about pulling a node out of the tree, think of deletion as rearranging the affected part of the tree while preserving the BST ordering rule.
The correct action depends on how many children the node has.
Case 1: The Node Has No Children
A node with no children is called a leaf node.
Because there are no subtrees below it, the node can simply be removed. The parent's reference to that node is changed to None.
This is the simplest deletion case.
Case 2: The Node Has One Child
If the node has exactly one child, that child can take the deleted node's place.
The parent's reference is updated so that it points directly to the deleted node's only child. The rest of the subtree remains connected, and the BST ordering rule is preserved.
Case 3: The Node Has Two Children
This is the case that makes BST deletion appear difficult.
If you simply move the left child or the right child into the deleted node's position, the subtree on the other side may no longer fit correctly. Both subtrees must remain connected, so we need a replacement value that preserves the ordering rule.
This is where the following two concepts are used:
- The inorder successor: the smallest value in the right subtree
- The inorder predecessor: the largest value in the left subtree
Most implementations use the inorder successor because the procedure is consistent and widely recognized.
Why Use the Inorder Successor?
The inorder successor is the smallest value that is greater than the value being deleted.
Suppose the node being deleted has a value of X. Every value in its left subtree is smaller than X, and every value in its right subtree is greater than X.
The replacement must continue to separate those two groups correctly. The smallest value in the right subtree is a good choice because it is still greater than every value in the left subtree, while being the closest larger value to the deleted one.
To find the inorder successor:
Move to the right child once, and then continue moving left until there is no left child.
That one sentence describes the entire search process.
Deletion of a node with two children then follows these steps:
- Find the inorder successor.
- Copy the successor's value into the node being deleted.
- Delete the successor from its original position.
A common mistake is to copy the successor's value and stop there. If you do that, the same value remains in two places in the tree. Copying the value is only a preparation step—the original successor node must still be removed.
There is another useful detail here: the inorder successor cannot have a left child. If it did, it would not be the leftmost and therefore smallest node in the right subtree.
As a result, deleting the successor always becomes one of the easier cases:
- It has no children.
- It has only a right child.
In other words, deleting a node with two children is really a technique for transforming a difficult deletion into a simpler zero-child or one-child deletion.
Python Example of BST Deletion
A safe and common implementation pattern is to make the deletion function return the updated root of the subtree.
This matters because the root itself may be deleted. If the function does not return the new root, the caller may lose track of the updated tree structure.
The following implementation uses the inorder successor when deleting a node with two children:
class Node: def __init__(self, val): self.val = val self.left = None self.right = None def find_min(node): """Return the node with the smallest value in a subtree.""" cur = node while cur.left: cur = cur.left return cur def delete(root, key): if root is None: return None if key < root.val: root.left = delete(root.left, key) return root if key > root.val: root.right = delete(root.right, key) return root # From this point, key == root.val. # The node to delete has been found. # Case 1: No children if root.left is None and root.right is None: return None # Case 2: One child if root.left is None: return root.right if root.right is None: return root.left # Case 3: Two children # Replace the value with the successor's value, # and then remove the successor from its original position. successor = find_min(root.right) root.val = successor.val root.right = delete(root.right, successor.val) return root
Common BST Deletion Mistakes
Most mistakes in BST deletion fall into a few predictable categories:
- Looking for the successor at the far right instead of the far left of the right subtree
- Copying the successor's value without deleting the original successor node
- Failing to handle deletion of the root
-
Forgetting to assign the returned subtree root back to the parent's
leftorrightreference
When debugging a deletion function, check these three questions first:
- Did the code follow the correct path to find the successor?
- After copying the successor's value, did it actually remove the original successor node?
- Does the deletion function return the updated root?
These checks are enough to identify many common BST deletion bugs.
BST Performance and the Importance of Balance
There is one practical limitation of ordinary binary search trees that is worth remembering.
If values are inserted in sorted order, the tree may continue growing in only one direction. For example, inserting 1, 2, 3, 4, 5 into a basic BST can produce a long chain of right children.
In that situation, search, insertion, and deletion may all take O(n) time instead of the expected O(log n) time.
This is why production software often uses self-balancing tree structures, such as red-black trees, rather than implementing a basic BST directly. Many standard map and set implementations are built on top of these balanced tree structures.
That does not make learning ordinary binary search trees any less valuable. Understanding the BST ordering rule—and especially the reasoning behind deletion—provides a strong foundation for learning balanced trees, sets, maps, and other ordered data structures.
The central idea is simple:
Compare values, choose the correct direction, and preserve the ordering rule after every operation.
Once that idea becomes familiar, searching and insertion feel natural, and even deletion becomes much easier to understand.
This article is also available in Korean: Read the Korean version