Binary Search Tree
A binary tree with one rule: every left descendant is smaller, every right descendant is larger. This ordering makes search, insert, and delete O(log n) on balanced trees and reveals how databases index data.
What is a BST?
A Binary Search Tree is a binary tree where every node satisfies the BST property: all values in the left subtree are strictly less than the node's value, and all values in the right subtree are strictly greater. This ordering is maintained for every node in the tree, not just each node relative to its immediate children.
The most important consequence: in-order traversal of a BST produces values in sorted ascending order. This means a BST implicitly represents a sorted sequence and any sorted-sequence operation — find minimum, find maximum, find successor, range query — can be implemented efficiently.
A perfectly balanced BST with n nodes has height ⌊log₂ n⌋, giving O(log n) search, insert, and delete. A degenerate BST where every node has only one child degrades to a linked list with O(n) operations. Balanced BST variants — AVL trees, Red-Black trees — use rotations after insert and delete to maintain O(log n) height. Rust's standard BTreeMap uses a B-tree, a disk-friendly generalisation that keeps between ⌈B/2⌉ and B keys per node.
Applications
Database indexes use B-trees (a BST generalisation) to support O(log n) lookup and sorted iteration over indexed columns. Rust's BTreeMap and BTreeSet implement ordered maps and sets using a balanced B-tree. BSTs support efficient rank queries (how many elements are less than x?) and order statistics (what is the kth smallest element?). Auto-complete systems store dictionary words in a BST to suggest lexicographically next words. Interval trees — BSTs augmented with max-endpoint information — power collision detection in graphics engines.
Representations
The linked node form directly mirrors the BST definition. Each node owns its left and right subtrees via Option<Box<BstNode>>.
#[derive(Debug)]
struct BstNode {
val: i32,
left: Option<Box<BstNode>>,
right: Option<Box<BstNode>>,
}
impl BstNode {
fn new(val: i32) -> Box<Self> {
Box::new(BstNode { val, left: None, right: None })
}
}
fn insert(root: Option<Box<BstNode>>, val: i32) -> Option<Box<BstNode>> {
match root {
None => Some(BstNode::new(val)),
Some(mut node) => {
if val < node.val {
node.left = insert(node.left.take(), val);
} else if val > node.val {
node.right = insert(node.right.take(), val);
}
// equal: do nothing (no duplicates)
Some(node)
}
}
}Operations and Time Complexity
| Operation | Average | Worst | Notes |
|---|---|---|---|
| Search | O(log n) | O(n) | Worst case: degenerate tree |
| Insert | O(log n) | O(n) | |
| Delete | O(log n) | O(n) | Three cases: leaf, one child, two children |
| Find min / max | O(log n) | O(n) | Leftmost / rightmost node |
| Inorder successor | O(log n) | O(n) | |
| In-order traversal | O(n) | O(n) | Produces sorted sequence |
| Range query | O(k + log n) | O(k + n) | k = result count |
Implementation in Rust
fn search(root: &Option<Box<BstNode>>, val: i32) -> bool {
match root {
None => false,
Some(node) => {
if val == node.val { true }
else if val < node.val { search(&node.left, val) }
else { search(&node.right, val) }
}
}
}
fn find_min(root: &Option<Box<BstNode>>) -> Option<i32> {
let mut curr = root;
let mut min_val = None;
while let Some(node) = curr {
min_val = Some(node.val);
curr = &node.left;
}
min_val
}
fn find_max(root: &Option<Box<BstNode>>) -> Option<i32> {
let mut curr = root;
let mut max_val = None;
while let Some(node) = curr {
max_val = Some(node.val);
curr = &node.right;
}
max_val
}
// Delete: three cases
// 1. Leaf: remove it
// 2. One child: replace with child
// 3. Two children: replace val with in-order successor (min of right subtree), delete successor
fn delete(root: Option<Box<BstNode>>, val: i32) -> Option<Box<BstNode>> {
match root {
None => None,
Some(mut node) => {
if val < node.val {
node.left = delete(node.left.take(), val);
Some(node)
} else if val > node.val {
node.right = delete(node.right.take(), val);
Some(node)
} else {
match (node.left.take(), node.right.take()) {
(None, right) => right,
(left, None) => left,
(left, right) => {
let min_val = find_min(&right).unwrap();
node.val = min_val;
node.right = delete(right, min_val);
node.left = left;
Some(node)
}
}
}
}
}
}
fn inorder(root: &Option<Box<BstNode>>, result: &mut Vec<i32>) {
if let Some(node) = root {
inorder(&node.left, result);
result.push(node.val);
inorder(&node.right, result);
}
}
fn main() {
let mut bst: Option<Box<BstNode>> = None;
for v in [5, 3, 7, 1, 4, 6, 8] {
bst = insert(bst, v);
}
let mut sorted = Vec::new();
inorder(&bst, &mut sorted);
println!("{:?}", sorted); // [1, 3, 4, 5, 6, 7, 8]
println!("min: {:?}", find_min(&bst)); // Some(1)
println!("max: {:?}", find_max(&bst)); // Some(8)
bst = delete(bst, 3);
let mut sorted2 = Vec::new();
inorder(&bst, &mut sorted2);
println!("{:?}", sorted2); // [1, 4, 5, 6, 7, 8]
}Fundamental Algorithms and Problems
Validate a BST
Check whether a given binary tree satisfies the BST property at every node. The common mistake is only comparing each node with its immediate children. The correct approach tracks a valid range (min, max) for each subtree: when entering the left child, the upper bound tightens to the parent's value; when entering the right child, the lower bound tightens.
fn is_valid_bst(root: &Option<Box<BstNode>>, min: i64, max: i64) -> bool {
match root {
None => true,
Some(node) => {
let v = node.val as i64;
if v <= min || v >= max { return false; }
is_valid_bst(&node.left, min, v) &&
is_valid_bst(&node.right, v, max)
}
}
}
fn validate(root: &Option<Box<BstNode>>) -> bool {
is_valid_bst(root, i64::MIN, i64::MAX)
}Kth Smallest Element
In-order traversal of a BST produces values in sorted order. The kth element visited in in-order traversal is the kth smallest. Use a mutable counter that decrements as nodes are visited.
fn kth_smallest(root: &Option<Box<BstNode>>, k: &mut usize) -> Option<i32> {
let node = root.as_ref()?;
if let Some(val) = kth_smallest(&node.left, k) { return Some(val); }
*k -= 1;
if *k == 0 { return Some(node.val); }
kth_smallest(&node.right, k)
}
fn main() {
let mut bst: Option<Box<BstNode>> = None;
for v in [5, 3, 7, 1, 4, 6, 8] { bst = insert(bst, v); }
println!("{:?}", kth_smallest(&bst, &mut 3)); // Some(4) (sorted: 1,3,4,5,6,7,8)
}Lowest Common Ancestor in a BST
The BST ordering makes LCA elegant: if both target values are less than the current node, the LCA is in the left subtree; if both are greater, it is in the right subtree; otherwise the current node is the LCA (the paths to the two targets diverge here).
fn lca_bst(root: &Option<Box<BstNode>>, p: i32, q: i32) -> Option<i32> {
let node = root.as_ref()?;
if p < node.val && q < node.val { return lca_bst(&node.left, p, q); }
if p > node.val && q > node.val { return lca_bst(&node.right, p, q); }
Some(node.val) // current node is the split point
}
fn main() {
let mut bst: Option<Box<BstNode>> = None;
for v in [6, 2, 8, 0, 4, 7, 9, 3, 5] { bst = insert(bst, v); }
println!("{:?}", lca_bst(&bst, 2, 8)); // Some(6)
println!("{:?}", lca_bst(&bst, 2, 4)); // Some(2)
println!("{:?}", lca_bst(&bst, 3, 5)); // Some(4)
}Count Nodes in Range [low, high]
Count nodes whose values fall in [low, high]. Prune branches: if the current node's value is less than low, all values in the left subtree are also less — skip left. If greater than high, skip right. Only recurse into a subtree when it might contain values in range.
fn range_count(root: &Option<Box<BstNode>>, low: i32, high: i32) -> usize {
match root {
None => 0,
Some(node) => {
let in_range = if node.val >= low && node.val <= high { 1 } else { 0 };
let left = if node.val > low { range_count(&node.left, low, high) } else { 0 };
let right = if node.val < high { range_count(&node.right, low, high) } else { 0 };
in_range + left + right
}
}
}
fn main() {
let mut bst: Option<Box<BstNode>> = None;
for v in [5, 3, 7, 1, 4, 6, 8] { bst = insert(bst, v); }
println!("{}", range_count(&bst, 3, 7)); // 4 (3, 4, 5, 6, 7 → 5 values)
println!("{}", range_count(&bst, 1, 4)); // 3 (1, 3, 4)
}BST to Sorted Array and Back
In-order traversal produces a sorted array. Building a balanced BST from a sorted array inserts the middle element as the root, then recursively does the same for the left and right halves — guaranteeing minimum possible height.
fn bst_to_sorted(root: &Option<Box<BstNode>>) -> Vec<i32> {
let mut result = Vec::new();
inorder(root, &mut result);
result
}
fn sorted_to_bst(arr: &[i32]) -> Option<Box<BstNode>> {
if arr.is_empty() { return None; }
let mid = arr.len() / 2;
let mut node = BstNode::new(arr[mid]);
node.left = sorted_to_bst(&arr[..mid]);
node.right = sorted_to_bst(&arr[mid+1..]);
Some(node)
}
fn main() {
let sorted = vec![1, 2, 3, 4, 5, 6, 7];
let balanced = sorted_to_bst(&sorted);
let back = bst_to_sorted(&balanced);
println!("{:?}", back); // [1, 2, 3, 4, 5, 6, 7]
}