Trees7 min read

Binary Search Tree

A sorted binary tree — left is smaller, right is bigger

search: \(O(\log n)\) avg / \(O(n)\) worstinsert: \(O(\log n)\) avgdelete: \(O(\log n)\) avgspace: \(O(n)\)

A Binary Search Tree (BST) is a binary tree with one extra rule that makes it incredibly useful: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

Think of it like a well-organized library catalog. At every junction you get a simple question: "Is what you're looking for smaller or bigger than this?" That one rule lets you cut your search space in half at every step.

The BST property

pseudocode

For every node N:
  all nodes in N.left  < N.value
  all nodes in N.right > N.value

This must hold for every node in the tree, not just the root. It's a recursive guarantee.

◈ Insert and search

← → arrow keys to step · click elements to interact

BST Insert, Search & In-order

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

def insert(root, v):
    if not root: return Node(v)
    if v < root.v: root.left  = insert(root.left,  v)
    elif v > root.v: root.right = insert(root.right, v)
    return root

def search(root, v):
    if not root: return False
    if v == root.v: return True
    return search(root.left, v) if v < root.v else search(root.right, v)

def inorder(root):
    return inorder(root.left) + [root.v] + inorder(root.right) if root else []

root = None
for v in [5, 3, 8, 1, 4, 7, 9]:
    root = insert(root, v)
print(inorder(root))   # [1,3,4,5,7,8,9] — sorted!
print(search(root, 4)) # True
print(search(root, 6)) # False

Output

[1, 3, 4, 5, 7, 8, 9]
True
False

Searching in a BST

Search starts at the root and asks one question per node: "Is the target smaller, bigger, or equal to the current node?"

Equal — found it!
Smaller — go left
Bigger — go right
Reached null — not in the tree

Each comparison eliminates roughly half the remaining nodes. In a balanced tree this gives \(O(\log n)\) time — like binary search on a sorted array, but in tree form.

Inserting into a BST

Insertion follows the same path as search. You walk down the tree using the same left/right rule until you find an empty slot, then place the new node there. The BST property is automatically preserved.

pseudocode

insert(node, val):
  if node is null: return new Node(val)
  if val < node.val: node.left  = insert(node.left,  val)
  if val > node.val: node.right = insert(node.right, val)
  return node

Deleting from a BST

Deletion has three cases depending on how many children the target node has:

No children (leaf) — just remove it.
One child — replace the node with its child.
Two children — find the in-order successor (smallest value in the right subtree), copy its value here, then delete the successor from the right subtree.

In-order gives sorted output

One of the most powerful properties of a BST: an in-order traversal (Left → Root → Right) always produces the values in ascending sorted order. A BST with values {5, 3, 8, 1, 4} visited in-order gives 1, 3, 4, 5, 8 — perfectly sorted!

Note: A BST is like a sorted phone book that organizes itself as you add entries. Every lookup, insert, and delete follows the same simple left-or-right decision path.

Complexity

Search (balanced)

Halve the search space at each step

Fast \(O(\log n)\)

Search (worst case)

Degenerate tree looks like a linked list

Slow \(O(n)\)

Insert (balanced)

Follow search path, attach at empty slot

Fast \(O(\log n)\)

Delete (balanced)

Find node + restructure with in-order successor

Fast \(O(\log n)\)

In-order traversal

Produces sorted output

Linear \(O(n)\)

Space

One node per value stored

Linear \(O(n)\)

When does a BST degrade?

If you insert values in sorted order (1, 2, 3, 4, 5...) every new node goes to the right child of the previous one. The tree becomes a straight line — effectively a linked list. All operations now cost \(O(n)\) instead of \(O(\log n)\).

This is why balanced BSTs (like AVL trees and Red-Black trees) exist — they automatically restructure themselves to prevent this degradation.

Use cases

Maintaining a sorted collection with frequent insertions and deletions
Range queries (find all values between X and Y)
In-order iteration over sorted data
As the basis for AVL trees, Red-Black trees, and treaps

BST Delete (3 Cases)

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

def insert(r, v):
    if not r: return Node(v)
    if v<r.v: r.left=insert(r.left,v)
    elif v>r.v: r.right=insert(r.right,v)
    return r

def delete(r, v):
    if not r: return r
    if v < r.v: r.left=delete(r.left, v); return r
    if v > r.v: r.right=delete(r.right, v); return r
    if not r.left: return r.right   # 0 or 1 child
    if not r.right: return r.left
    # 2 children: find in-order successor (min of right subtree)
    succ = r.right
    while succ.left: succ = succ.left
    r.v = succ.v
    r.right = delete(r.right, succ.v)
    return r

def inorder(r): return inorder(r.left)+[r.v]+inorder(r.right) if r else []

root = None
for v in [5,3,8,1,4,7,9]: root = insert(root, v)
root = delete(root, 3)  # node with two children
print(inorder(root))    # [1,4,5,7,8,9]