Binary Search Tree (BST)

A tree that keeps smaller values left and larger ones right for fast search and sorted traversal.

Worth knowing first

#How does it work?

A binary search tree (BST) is a tree where every node has at most two children. Its rule is simple: every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger.

Thanks to this rule, searching is like binary search: start at the root, go left if the target is smaller and right if it's larger. Each step discards part of the tree.

Walking the tree in-order (left, node, right) yields the values from smallest to largest. So a BST gives you both fast search and sorted data.

#Try it yourself

$ binary_search-tree --interactive

Type a value and insert or search it. At every node, smaller values go left and larger ones go right.

Elements: 7/12VisitingNewRemovingFound / read

#Basic operations

insert(x)
Starts at the root, goes left if smaller and right if larger, and adds a new leaf at the empty spot.
search(x)
Follows the same path; finds the value or reaches an empty branch.
remove(x)
A leaf is simply removed; a node with one child is replaced by that child; a node with two children gets the smallest value of its right subtree (the successor).
inorder
Visits the left subtree, the node, then the right subtree; values come out sorted.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    left: Node | None = None
    right: Node | None = None


def insert(node: Node | None, value: int) -> Node:
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node  # duplicates are ignored


def contains(node: Node | None, value: int) -> bool:
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False


def remove(node: Node | None, value: int) -> Node | None:
    if node is None:
        return None
    if value < node.value:
        node.left = remove(node.left, value)
    elif value > node.value:
        node.right = remove(node.right, value)
    elif node.left and node.right:
        # Two children: copy the in-order successor, then remove it from the right subtree.
        succ = node.right
        while succ.left:
            succ = succ.left
        node.value = succ.value
        node.right = remove(node.right, succ.value)
    else:
        # Zero or one child: the child (or None) takes this node's place.
        return node.left or node.right
    return node


def inorder(node: Node | None) -> list[int]:
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


root = None
for v in (50, 30, 70, 20, 40, 60, 80):
    root = insert(root, v)

print(*inorder(root))  # sorted order
print(str(contains(root, 60)).lower())
root = remove(root, 50)  # the root has two children
print(*inorder(root))

#Complexity

OperationTime
Search / insert / remove (balanced)O(log n)
Search / insert / remove (worst, unbalanced)O(n)
Minimum / maximumO(h)
In-order walkO(n)
MemoryO(n)

Every operation takes as long as the tree's height (h). In a balanced tree h ≈ log₂ n. But if values are inserted in order (1, 2, 3, ...) every node goes right, the tree becomes a list and h = n. AVL and red-black trees rebalance themselves to guarantee O(log n). Try inserting 10, 20, 30, 40 in order.

#When to use it?

Good for data that must stay sorted while changing often: sorted sets and maps (Java's TreeMap and C++'s std::map use red-black trees), range queries ("everything between 30 and 60"), finding the nearest smaller or larger value. Database indexes use B-trees, a disk-friendly relative.

#Practice

Log in to answer questions and save your progress.

Easy

1/3

What is true about the values in a BST node's left subtree?

  • 1They are all smaller than the node
  • 2They are all larger than the node
  • 3They are random
  • 4They are all equal

Medium

1/1

Inserting 50, 30, 70, 40 into an empty BST, whose child does 40 become?

  • 130's right child
  • 270's left child
  • 350's left child
  • 430's left child

Hard

1/1

If 1, 2, 3, 4, 5 are inserted in order into an empty BST, what does search degrade to?

  • 1O(n), the tree becomes a list
  • 2O(log n), the tree stays balanced
  • 3O(1)
  • 4O(n log n)

#Up next

Lessons that build on this one: