Binary search tree

avg O(log n)

A binary search tree (BST) stores values so that, for every node, the whole left subtree is smaller and the whole right subtree is larger. That ordering lets insert, search, and delete each follow a single root-to-leaf path — O(log n) on average for a balanced tree, but O(n) if it degenerates into a chain. Deleting a node with two children swaps in its in-order successor.

Binary search tree
Press ▶ to run
Edit the input and press Play

How it works

  1. To insert or search, start at the root and go left when the value is smaller, right when larger.
  2. Insert drops the value into the first empty spot it reaches.
  3. Search stops when it matches a node or falls off the tree.
  4. Delete splices out a node, replacing a two-child node with its in-order successor.

Pseudocode

1insert(v):                          # avg O(log n)2  walk from the root: go left if v < node, else right3  drop v into the first empty spot45search(v):6  walk the same way until v is found or you fall off78delete(v):9  0 / 1 child: splice the node out10  2 children: replace it with its in-order successor