Binary Search Tree

A rooted binary tree where each node's left subtree has smaller keys and right subtree has larger keys.

O(log n)Trees
Phase 1f(x)

The Mathematics

BST property, insertion and search, and height analysis

BST Property

For every node vv in a Binary Search Tree:

∀ u∈left(v):u.key<v.keyand∀ w∈right(v):w.key≥v.key\forall\, u \in \text{left}(v): u.\text{key} < v.\text{key} \quad \text{and} \quad \forall\, w \in \text{right}(v): w.\text{key} \geq v.\text{key}

This invariant enables efficient search by eliminating half the remaining tree at each comparison.

Search

To search for key kk, compare with the current node and recurse:

∙\bullet If k=v.keyk = v.\text{key}: found

∙\bullet If k<v.keyk < v.\text{key}: search left subtree

∙\bullet If k>v.keyk > v.\text{key}: search right subtree

Tsearch=O(h)T_{\text{search}} = O(h)

Insertion

Insertion follows the same path as search. When we reach a nil\text{nil} pointer, we create a new leaf node:

insert(v,k)={Node(k)if v=nilinsert leftif k<v.keyinsert rightotherwise\text{insert}(v, k) = \begin{cases} \text{Node}(k) & \text{if } v = \text{nil} \\ \text{insert left} & \text{if } k < v.\text{key} \\ \text{insert right} & \text{otherwise} \end{cases}

Height Analysis

All operations take O(h)O(h) time, where hh is the tree height:

Best case (balanced): h=⌊log⁡2n⌋⇒O(log⁡n)h = \lfloor \log_2 n \rfloor \Rightarrow O(\log n)

Worst case (degenerate): h=n−1⇒O(n)h = n - 1 \Rightarrow O(n) (inserting sorted data creates a linked list)

Self-balancing trees (AVL, Red-Black) guarantee h=O(log⁡n)h = O(\log n) after every operation, ensuring worst-case O(log⁡n)O(\log n) performance.

Phase 2▶

See It Work

Building a BST by inserting [5, 3, 7, 1, 4, 6, 8]

empty tree
Inserting: 5
root=nil⇒create node(5)\text{root} = \text{nil} \Rightarrow \text{create node}(5)
Step 1 of 8

Empty tree. Insert 5 as the root node.

Phase 3</>

The Code

Mapping BST operations to recursive Python functions

Mathematical Formulation

root=nil⇒Node(k)\text{root} = \text{nil} \Rightarrow \text{Node}(k)

Base case: empty subtree — create a new leaf node

k<root.key⇒insert leftk < \text{root.key} \Rightarrow \text{insert left}

BST property: smaller keys go in the left subtree

k≥root.key⇒insert rightk \geq \text{root.key} \Rightarrow \text{insert right}

BST property: larger keys go in the right subtree

root.key=k⇒found\text{root.key} = k \Rightarrow \text{found}

Search: if current node matches, return it

T(n)=O(h),  h=O(log⁡n) balancedT(n) = O(h),\; h = O(\log n) \text{ balanced}

Operations take O(height) time — O(log n) when balanced

Python Implementation

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

def insert(root, key):
    if root is None:
        return Node(key)              # Create leaf
    if key < root.key:
        root.left = insert(root.left, key)   # Go left
    else:
        root.right = insert(root.right, key) # Go right
    return root

def search(root, key):
    if root is None or root.key == key:
        return root                    # Found or miss
    if key < root.key:
        return search(root.left, key)  # Search left
    return search(root.right, key)     # Search right