Overview
A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key.
Core Concepts
- Root: The topmost node of the tree.
- Leaf: A node with no children.
- In-Order Traversal: Visiting the left subtree, then the root, then the right subtree. In a BST, this results in the elements being visited in sorted order.
- Balance: A tree is balanced if the heights of the left and right subtrees of every node differ by no more than one. Balanced trees (like AVL or Red-Black trees) prevent performance degradation.
- Time Complexity:
- Search: $O(\log n)$ average / $O(n)$ worst case (if the tree is a “skewed” line).
- Insertion: $O(\log n)$ average / $O(n)$ worst case.
- Deletion: $O(\log n)$ average / $O(n)$ worst case.
Code Examples
class BSTNode {
value: number;
left: BSTNode | null = null;
right: BSTNode | null = null;
constructor(val: number) { this.value = val; }
}
function insert(root: BSTNode | null, val: number): BSTNode {
if (!root) return new BSTNode(val);
if (val < root.value) root.left = insert(root.left, val);
else root.right = insert(root.right, val);
return root;
}Use Cases
- Dynamic Sets: Maintaining a sorted list of elements where insertions and deletions are frequent.
- Priority Queues: BSTs (specifically Heaps, which are similar) are used to implement priority queues.
- Symbol Tables: Used in compilers to store identifiers.
Gotchas
- Degeneration: If elements are inserted in sorted order (e.g., 1, 2, 3, 4, 5), the BST becomes a linked list, and search time drops to $O(n)$.
- Deletion Complexity: Removing a node with two children requires finding the “in-order successor” (the smallest node in the right subtree) to replace it.