Binary Search Tree

DSA · Intermediate

Definition

A BST keeps smaller keys in the left subtree and larger keys in the right subtree.

Supports ordered search, insert and delete in O(log n) when balanced.

Diagram

Flowchart

Example: Insert + inorder

def ins(n, v):
    if not n: return [v, None, None]
    if v < n[0]: n[1] = ins(n[1], v)
    else: n[2] = ins(n[2], v)
    return n
def ino(n):
    return ino(n[1]) + [n[0]] + ino(n[2]) if n else []
r = None
for v in [8, 3, 10, 1, 6]: r = ins(r, v)
print(ino(r))

Output: [1, 3, 6, 8, 10]

Complexity

Balanced O(log n) · Skewed O(n)

Key points

Inorder traversal is sorted
AVL/Red-Black trees stay balanced

Interview questions

Validate a BST?

Pass min/max bounds down recursively, or check inorder is strictly increasing.