Binary Search Tree (BST) — BST property, insert, search, delete (3 cases)

WHY does the BST property exist?

WHAT we want: a data structure that supports search, insert, delete all fast (ideally $O(\log n)$ ), while staying dynamic (sizes change).

A sorted array gives $O(\log n)$ search (binary search) but $O(n)$ insert/delete (shifting).
A linked list gives $O(1)$ insert but $O(n)$ search.

WHY the property helps: If we keep the invariant "left < node < right", then at any node we can decide a direction by one comparison. Going left or right discards an entire subtree. If the tree is balanced, depth is $\log n$ , so all operations cost $O(\log n)$ .

Figure — Binary Search Tree (BST) — BST property, insert, search, delete (3 cases)

Search — derive it from the property

def search(node, t):
    while node is not None:
        if t == node.key:
            return node
        node = node.left if t < node.key else node.right
    return None      # not present

Why this step? Each comparison uses the invariant to eliminate one whole subtree, so we follow a single root-to-leaf path. Cost = path length = $O(h)$ where $h$ = height.

Insert — search, then attach at the empty spot

def insert(root, v):
    if root is None:
        return Node(v)
    if v < root.key:
        root.left = insert(root.left, v)
    elif v > root.key:
        root.right = insert(root.right, v)
    # v == root.key: duplicate, ignore (or handle as you like)
    return root

Why this step? We descend exactly like search, preserving the invariant on the way down. New nodes are always inserted as leaves, so no existing relationships break. Cost $O(h)$ .

Delete — the 3 cases (the heart of BSTs)

First find the node. Then handle by number of children.

def find_min(node):          # leftmost node
    while node.left is not None:
        node = node.left
    return node
 
def delete(root, v):
    if root is None:
        return None
    if v < root.key:
        root.left = delete(root.left, v)
    elif v > root.key:
        root.right = delete(root.right, v)
    else:                                # found node to delete
        if root.left is None:            # Case 1 & 2 (no left child)
            return root.right
        if root.right is None:           # Case 2 (no right child)
            return root.left
        succ = find_min(root.right)      # Case 3: in-order successor
        root.key = succ.key              # copy successor key up
        root.right = delete(root.right, succ.key)  # delete successor
    return root

Why this step?

return root.right when no left child cleanly covers leaf (both None → returns None) and one-child cases. Elegant unification.
In Case 3 the successor is the leftmost node of the right subtree, so it has no left child → deleting it is always Case 1 or 2. The recursion can never loop forever.

Steel-manning the BST-validation mistake

Common mistake "Just check each node vs its two children"

Why it feels right: the property is stated in terms of children (left.key < key < right.key), so checking only children seems sufficient. Counter-example:

       10
      /  \
     5    15
         /
        6      <-- 6 < 10 but it's in the RIGHT subtree!

Each node passes the local child check, yet 6 violates the property w.r.t. ancestor 10. Fix: validate with a range: every node must lie in $(low, high)$ ; recurse left with $high = key$ , right with $low = key$ .

def is_bst(node, low=float('-inf'), high=float('inf')):
    if node is None: return True
    if not (low < node.key < high): return False
    return is_bst(node.left, low, node.key) and \
           is_bst(node.right, node.key, high)

Active recall

Recall Predict before peeking

Why does going left/right discard half the work?
Where is a newly inserted key always placed?
Why is the in-order successor guaranteed to have ≤ 1 child?
What's the worst-case height and when does it happen?

Answers: (1) the invariant guarantees the target can only be on one side; (2) as a leaf; (3) it's the leftmost node of the right subtree, so it has no left child; (4) $n-1$ , when keys are inserted in sorted/reverse-sorted order (degenerate stick).

Recall Feynman: explain to a 12-year-old

Imagine a guessing game where numbers are kept on shelves. Every shelf has a number. Smaller numbers go on the shelf to the left, bigger ones to the right — and this rule repeats for every shelf. To find a number you start at the top and keep asking "is it smaller or bigger?", stepping left or right. Each step you skip a whole pile of shelves, so you find it super fast. To remove a shelf that has two shelves hanging off it, you sneak in the next-bigger number from the right side to take its place, because that's the only number that keeps everyone in the right order.

Flashcards

What is the BST property (state it precisely)?

For every node, all keys in its left subtree are strictly less, and all keys in its right subtree are strictly greater than the node's key — recursively for every node.

What traversal of a BST yields sorted order?

In-order (left, node, right) gives strictly increasing keys.

Why is BST search

O(h)

and not

O(\log n)

guaranteed?

We follow one root-to-leaf path of length = height

h

;

h

is only

\log n

if the tree is balanced, else up to

n-1

Where is a new key inserted in a BST?

Always as a new leaf, at the spot where a search for that key falls off the tree (hits None).

Delete Case 1 (leaf)?

Remove the node; set parent's pointer to None.

Delete Case 2 (one child)?

Splice it out — connect the node's single child directly to its parent.

Delete Case 3 (two children)?

Replace node's key with its in-order successor (min of right subtree), then delete that successor node, which has ≤1 child.

Why must the successor in Case 3 have at most one child?

It is the leftmost node of the right subtree, so it has no left child.

Why doesn't checking only direct children validate a BST?

A node can satisfy its parent but violate a distant ancestor's range; you must check value ranges propagated down.

When does a BST degenerate to

O(n)

operations?

When keys are inserted in (reverse-)sorted order, producing a linear "stick"; fixed by self-balancing (AVL/Red-Black).

In-order successor of a node with a right subtree is found how?

Go right once, then keep going left until no left child (find_min of right subtree).

Connections

Binary Tree — terminology & traversals (in-order is the BST sorted walk)
Binary Search on Sorted Array (same halving idea, static data)
AVL Tree and Red-Black Tree (self-balancing fix for degenerate BSTs)
Tree Height vs Depth (why $h$ drives all costs)
Heap vs BST (heap orders parent–child by priority, not left/right by value)
Recursion on Trees (delete/insert as return-the-subtree pattern)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

BST ka basic funda ek hi line mein: har node ke left mein chhote, right mein bade keys. Aur yeh rule sirf direct children ke liye nahi, poore subtree ke liye chalta hai (recursively). Isi wajah se jab tum kisi key ko dhoondhte ho, har node pe sirf ek comparison karke aadha tree foran phenk dete ho — bilkul binary search jaisa, par yahan insert/delete bhi sasta hai.

Search simple hai: root se start karo, target chhota hai toh left jao, bada hai toh right, milne tak ya None aane tak. Insert bhi search hi hai — jahan search "gir jaata hai" (None slot), wahin naya leaf laga do, isse purane connections kabhi nahi tootte. Ek important baat: agar keys sorted order mein insert karoge toh tree ek seedhi line (stick) ban jaayega aur sab kuch $O(n)$ ho jaayega — isi problem ka solution AVL/Red-Black trees hain.

Delete mein 3 cases yaad rakho: (1) leaf ho toh seedha kaat do; (2) ek child ho toh us child ko parent se direct jod do (lift kar do); (3) do children ho toh node ki value ko uske in-order successor (right subtree ka sabse chhota) se replace karo, phir us successor ko delete karo — wo successor hamesha leftmost hota hai isliye uska left child nahi hota, matlab wo Case 1 ya 2 mein simat jaata hai. Yeh trick order ko intact rakhti hai.

Ek classic galti: log socht hain "bas node vs uske do children check kar lo, BST valid hai" — galat! Door ka ancestor violate ho sakta hai. Sahi tareeka hai har node ko ek range (low, high) ke andar check karna. Yaad rakho: "Left-Less, Right-Right" aur delete ke liye "0 = cut, 1 = lift, 2 = swap-with-successor."

Binary Search Tree (BST) — BST property, insert, search, delete (3 cases)

WHY does the BST property exist?

Search — derive it from the property

Insert — search, then attach at the empty spot

Delete — the 3 cases (the heart of BSTs)

Steel-manning the BST-validation mistake

Active recall

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Trees

Connections