Binary Search Trees (BST)

A Binary Search Tree is a node-based data structure where each node has at most two children, and every left child is smaller than its parent while every right child is larger.

Core Properties

Left subtree contains only nodes with keys less than the parent node.
Right subtree contains only nodes with keys greater than the parent node.
No duplicate keys (in the standard definition).
Both left and right subtrees are themselves valid BSTs.

Common Operations

Insert

Start at the root and compare the new value. Go left if smaller, right if larger, until an empty spot is found.

Search

Same traversal logic as insert — return true if the value is found, false if a null node is reached.

Delete

Three cases: leaf node (remove directly), one child (replace with child), two children (replace with in-order successor).

Time Complexities

Search: O(log n) average, O(n) worst case (unbalanced)
Insert: O(log n) average, O(n) worst case
Delete: O(log n) average, O(n) worst case

BST Diagram

A sample BST — note how left children are always smaller than their parent.

Learn More

For a deeper dive, visit the Wikipedia page on Binary Search Trees.