TreesTrees

Binary Search Tree

A binary tree where every left descendant is smaller and every right descendant is larger, giving O(h) ordered search, insert and delete.

Learn Binary Search Tree →
Empty tree
1/52Start with an empty BST. Invariant: every node's left subtree holds smaller keys and its right subtree larger keys.
Comparing hereComparison pathNewly insertedFound / successorBeing deleted
PseudocodeLearn Binary Search Tree →
1node = root
2while node: compare key with node.value
3  go left if key < node.value, right if key > node.value
4insert: attach new leaf at the null position reached
5search: found if key == node.value, else not found at null
6delete leaf: unlink it
7delete node with one child: splice child into its place
8delete node with two children: replace with inorder successor (min of right subtree)
Variables
size0
Complexity
access O(log n)
search O(log n)
insert O(log n)
delete O(log n)
Speed