Binary Search Trees

Analogy categoryAnalogies

Introduction

A binary search tree (BST) is a binary tree that maintains a key ordering invariant: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value. This invariant makes BSTs a natural fit for implementing ordered sets, maps, and priority-based lookups. When a BST is reasonably balanced, search, insertion, and deletion all run in O(log n) time, which is why BSTs (and their self-balancing variants like AVL and red-black trees) underpin many standard library map and set implementations.

🏏

Cricket analogy: A BST is like organizing a squad list so every player to the left of a benchmark has a lower batting average and everyone to the right has a higher one, letting a selector find any player's rank in O(log n) comparisons when the squad is well balanced.

Structure/Syntax

python

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return BSTNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        # duplicates ignored
        return node

Explanation

Insertion walks down from the root, comparing the new value against each node: going left if smaller, right if larger, until it finds an empty spot to attach the new node. Search follows the exact same comparison logic, so it can skip entire subtrees at every step, similar to binary search on a sorted array. Deletion is more involved and has three cases: deleting a leaf (simply remove it), deleting a node with one child (replace the node with its child), and deleting a node with two children (replace the node's value with its in-order successor — the smallest value in the right subtree — then delete that successor node).

🏏

Cricket analogy: Inserting a new player into a ranked squad list walks down comparing career averages, going left if lower and right if higher, until an empty slot opens; dropping a retiring vice-captain (two 'children' in influence) means promoting the next-best player up from the right branch to fill the gap.

Example

python

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)


bst = BinarySearchTree()
for v in [8, 3, 10, 1, 6, 14, 4, 7]:
    bst.insert(v)

found = search(bst.root, 6)
print(found.value if found else "not found")  # 6

Complexity

For a balanced BST, search, insert, and delete each run in O(log n) time because each comparison eliminates roughly half of the remaining nodes, and O(log n) space for the recursion stack. However, if values are inserted in sorted (or reverse-sorted) order without rebalancing, the BST degenerates into a linked list, and all operations drop to O(n) worst case. This vulnerability is exactly why self-balancing BSTs such as AVL trees and red-black trees exist — they guarantee O(log n) height regardless of insertion order.

🏏

Cricket analogy: A well-balanced squad-ranking BST resolves any player lookup in O(log n) comparisons because each check eliminates half the remaining candidates, but if players were added in strictly increasing batting-average order with no rebalancing, the structure degenerates into a single chain and lookups become O(n), exactly why balanced structures like AVL exist for team databases.

Key Takeaways

BST invariant: left subtree < node < right subtree, for every node.
Search, insert, and delete all follow a root-to-leaf comparison path.
Deletion has three cases: leaf, one child, two children (use in-order successor).
Average/balanced case is O(log n); worst case (skewed) is O(n).

Practice what you learned

1. In a valid binary search tree, where must all values in the left subtree of a node lie?

2. When deleting a BST node that has two children, what is the standard replacement strategy?

3. What is the worst-case time complexity of searching in an unbalanced BST built by inserting sorted data?

4. What is the average-case time complexity of insertion into a balanced BST?

Was this page helpful?

Binary Trees

Tree Traversals

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#BinarySearchTrees#Binary#Search#Trees#Structure#StudyNotes#SkillVeris