16. Binary Search Trees

What problem does this solve? Linear search is O(n). Binary search on sorted arrays is O(log n) but insert/delete is O(n). A Binary Search Tree (BST) enables O(log n) search, insert, AND delete — combining the best of both worlds.

1. BST Property

• Left subtree values < node value
• Right subtree values > node value
• Both subtrees are also BSTs (Diagram)

2. Implementation

python
Run Inline
# runnable
class BSTNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
class BST:
    def __init__(self):
        self.root = None
        self._size = 0
    def __len__(self):
        return self._size
    # ---- Search ----
    def search(self, val):
        """Return True if val exists in BST. O(h) where h = height."""
        curr = self.root
        while curr:
            if curr.val == val:
                return True
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return False
    # ---- Insert ----
    def insert(self, val):
        """Insert val into BST. O(h)."""
        if self.root is None:
            self.root = BSTNode(val)
            self._size += 1
            return
        curr = self.root
        while True:
            if val < curr.val:
                if curr.left is None:
                    curr.left = BSTNode(val)
                    self._size += 1
                    return
                curr = curr.left
            elif val > curr.val:
                if curr.right is None:
                    curr.right = BSTNode(val)
                    self._size += 1
                    return
                curr = curr.right
            else:
                return  # No duplicates
    # ---- Delete ----
    def delete(self, val):
        """Delete val from BST. O(h)."""
        self.root = self._delete(self.root, val)
    def _delete(self, node, val):
        if node is None:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # Found — 3 cases
            if node.left is None:
                self._size -= 1
                return node.right  # Case 1 & 2: 0 or 1 child (right)
            if node.right is None:
                self._size -= 1
                return node.left   # Case 2: 1 child (left)
            # Case 3: 2 children — find inorder successor
            successor = self._min_node(node.right)
            node.val = successor.val
            node.right = self._delete(node.right, successor.val)
            # Note: _size is decremented in the recursive call
        return node
    def _min_node(self, node):
        """Find node with minimum value in subtree."""
        while node.left:
            node = node.left
        return node
    # ---- Traversals ----
    def inorder(self):
        """Return sorted list of values."""
        result = []
        def _traverse(n):
            if n:
                _traverse(n.left)
                result.append(n.val)
                _traverse(n.right)
        _traverse(self.root)
        return result
# Test
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(v)
print(f"Inorder: {bst.inorder()}")     # [20, 30, 40, 50, 60, 70, 80]
print(f"Search 40: {bst.search(40)}")  # True
print(f"Search 99: {bst.search(99)}")  # False
bst.delete(20)
print(f"After delete 20: {bst.inorder()}")  # [30, 40, 50, 60, 70, 80]
bst.delete(50)
print(f"After delete 50: {bst.inorder()}")  # [30, 40, 60, 70, 80]

Delete — The Three Cases

3. Complexity

Practice Questions

Answers

A1.

pseudo
        5
      /   \
     3     7
    / \   / \
   1   4 6   8

A2. Worst: O(n) (skewed). Best: O(log n) (perfectly balanced).

A3. Inorder successor of 50 is 60. Replace 50 with 60, delete original 60.

A4. Do inorder traversal and stop at the k-th element.

A5. Inorder traversal (left → root → right) produces values in ascending order. Join Discord Previous15. Binary Trees & TraversalsNext17. AVL Trees — Self-Balancing BSTs