Binary Search Trees

Jr Codex DSA Notes

Level: Intermediate–Advanced Prerequisites: Chapter 2 Time to complete: ~30 minutes

Table of Contents

1. The BST Property
2. Search
3. Insert
4. Delete
5. Complexity: Balanced vs. Skewed
6. Practice: Validate a BST
7. Summary & Next Steps

1. The BST Property

A binary search tree (BST) is a binary tree (Chapter 1) with one added rule, true at every node: everything in the left subtree is smaller, everything in the right subtree is larger.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

This single rule is what makes search efficient — at each node, comparing the target to the current value tells you which subtree to explore, discarding the other half entirely (the same "eliminate half the possibilities" idea behind binary search from Module 3).

2. Search

def search(node, target):
    if node is None or node.value == target:
        return node
    if target < node.value:
        return search(node.left, target)
    return search(node.right, target)
    # O(h) time, where h is the tree's height (Chapter 1) — O(1) space if written
    # iteratively, O(h) space here due to the recursive call stack

Each comparison eliminates an entire subtree — exactly why a balanced BST gives O(log n) search, mirroring Module 1 Chapter 2's binary search discussion.

3. Insert

def insert(node, value):
    if node is None:
        return Node(value)          # found the empty spot — place the new node here
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node                      # duplicates are ignored in this version
    # O(h) time — descends at most h levels before finding an empty spot

Building a BST from a list is just repeated insertion:

def build_bst(values):
    root = None
    for value in values:
        root = insert(root, value)
    return root
    # O(n × h) time overall

4. Delete

Deletion has three cases, and it's the trickiest of the three operations because removing a node must preserve the BST property for everything that remains:

def find_min(node):
    while node.left is not None:
        node = node.left
    return node
 
def delete(node, value):
    if node is None:
        return None
 
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        # Found the node to delete — three cases:
        if node.left is None:            # Case 1: no left child (0 or 1 children)
            return node.right
        if node.right is None:            # Case 2: no right child
            return node.left
        # Case 3: two children — replace value with the inorder successor
        # (the smallest value in the right subtree), then delete THAT node instead
        successor = find_min(node.right)
        node.value = successor.value
        node.right = delete(node.right, successor.value)
 
    return node
    # O(h) time

Why the inorder successor? It's the smallest value greater than node.value — swapping it in preserves the BST property on both sides without having to reshuffle the rest of the tree. (The inorder predecessor — the largest value in the left subtree — would work just as well.)

5. Complexity: Balanced vs. Skewed

This is where Chapter 1's balanced-vs-skewed discussion and Module 1 Chapter 5's best/worst-case framing meet directly:

Inserting already-sorted data (1, 2, 3, 4, 5...) into an empty BST using the insert function above produces a completely skewed tree — every new value is larger than everything before it, so it always goes right, and the tree degenerates into what is structurally a linked list (Module 6). Self-balancing variants (AVL trees, Red-Black trees) solve this by rebalancing after every insert/delete, guaranteeing O(log n) in the worst case too — worth knowing they exist, though implementing one is outside this curriculum's interview-prep scope.

6. Practice: Validate a BST

Problem: Given a binary tree, determine whether it satisfies the BST property everywhere — not just locally (comparing each node to its immediate children), but globally.

A common bug: checking only node.left.value < node.value < node.right.value misses violations further down, like a right-subtree node that's smaller than an ancestor two levels up. The fix is to track a valid (low, high) range that narrows as you descend:

def is_valid_bst(node, low=float('-inf'), high=float('inf')):
    if node is None:
        return True
    if not (low < node.value < high):
        return False
    return (is_valid_bst(node.left, low, node.value) and
            is_valid_bst(node.right, node.value, high))
    # O(n) time — every node visited once; O(h) space for the call stack

Each recursive call narrows the allowed range: descending left tightens the high bound to the parent's value; descending right tightens the low bound. This correctly catches violations anywhere in the tree, not just at adjacent parent-child pairs.

7. Summary & Next Steps

Key Takeaways

• The BST property (left < node < right, at every node) is what makes search efficient by eliminating half the remaining tree at each comparison.
• Search, insert, and delete are all O(h) — which is O(log n) for a balanced tree but degrades to O(n) for a skewed one.
• Deleting a two-child node works by swapping in the inorder successor (or predecessor), then deleting that simpler node instead.
• Validating a BST requires tracking a valid range at each node, not just comparing immediate parent-child pairs.

Concept Check

1. Why does inserting already-sorted values into a plain BST produce a skewed tree?
2. Why does deleting a two-child node use the inorder successor instead of just removing it directly?
3. Why does checking only node.left.value < node.value < node.right.value fail to correctly validate a BST?

Next Chapter

→ Chapter 4: Heaps & Priority Queues

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index