Lesson 10 / 42

Binary Search Tree

A binary tree where left < node < right, giving ordered O(log n) search.

By · 15 years in web development · Updated 1 Oct 2026

The ordering invariant

For every node, all keys in its left subtree are smaller and all in its right are larger. So searching is like binary search: compare, then go left or right, halving the tree each step — O(h).

Search & insert

Both follow one path from the root; insert drops the new key where the search would have failed.

def search(node, key):
    while node and node.val != key:
        node = node.left if key < node.val else node.right
    return node

def insert(node, key):
    if not node: return Node(key)
    if key < node.val: node.left = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node

In-order = sorted

An in-order traversal of a BST yields keys in ascending order. That's a quick way to validate a BST or find the k-th smallest element.

Quick check: Insert 1,2,3,4,5 in order into an empty unbalanced BST. Search cost becomes...

  • O(log n)
  • O(n)
  • O(1)
  • O(n log n)
Answer

O(n) — Sorted inserts create a right-leaning chain — effectively a linked list. Balanced trees (AVL, red-black) fix this.