A binary search tree (BST) is a hierarchical data structure in which each node has at most two children. It organizes values by an ordering rule: values smaller than a node belong in its left subtree, while larger values belong in its right subtree.
A BST consists of nodes connected by edges. The node is the root, and nodes without children are leaves. Every subtree must satisfy the same BST invariant.
For example, insert 8, 3, 10, 1, 6 and 14:
- 8 becomes the root.
- 3 is placed left of 8, and 10 right of 8.
- 1 is placed left of 3, and 6 right of 3.
- 14 is placed right of 10.
To search for 6, compare it with 8. Because 6 is smaller, move left to 3; because it is larger than 3, move right and find 6. Each comparison excludes one subtree.
| BST case | Organization and performance |
|---|---|
| Balanced tree | Height is approximately , so search, insertion and deletion are typically . |
| Skewed tree | Nodes may form a chain, giving height and worst-case operations of . |
| Duplicate value | Use a consistent policy, such as storing a count or always choosing one side. |
An in-order traversal visits the left subtree, the node, then the right subtree. In a BST, this outputs values in ascending order.
A common misconception is that every binary tree is a BST. A binary tree only limits each node to two children; a BST also enforces the ordering invariant.
For an IB B4.1 response, define the node relationship, apply the ordering rule to an insertion or search, and distinguish the abstract data type (ADT) from its implementation. A BST can implement a set or map. When discussing efficiency, relate time complexity to tree height; do not claim that every BST search is .
