DSA · Chapter 21 of 40
Binary Search Trees
In a binary search tree every value in the left subtree is smaller than the node and every value in the right subtree is larger. This ordering lets search, insert and delete run in O(h), where h is the height.
If keys arrive in sorted order the tree degenerates into a linked list and operations become O(n), which is why self-balancing trees exist.
Search
Compare with the node: go left if smaller, right if larger, stop when equal or None. Each step discards half the remaining tree in a balanced BST.
Deletion cases
A leaf is removed directly; a node with one child is replaced by that child; a node with two children is replaced by its inorder successor.
Example 1 (python)
def insert(node, val):
if node is None:
return Node(val)
if val < node.val:
node.left = insert(node.left, val)
else:
node.right = insert(node.right, val)
return node
bst = None
for v in [8, 3, 10]:
bst = insert(bst, v)
print(bst.val, bst.left.val, bst.right.val)Output
8 3 10Insertion walks down and attaches a new leaf.
Example 2 (python)
def search(node, val):
while node:
if val == node.val:
return True
node = node.left if val < node.val else node.right
return False
print(search(bst, 10), search(bst, 5))Output
True FalseSearch is O(h) and needs no recursion.
Key points
- Left subtree < node < right subtree.
- Search, insert and delete are O(h).
- A balanced BST gives O(log n); a skewed one gives O(n).
- Deleting a two-child node uses the inorder successor.
💡 Note: Validating a BST needs min/max bounds, not just parent comparisons.