Binary Search Tree

Definition

A binary search tree (BST) is a node-based data structure in which each node has at most two children, and every node's left subtree contains only values less than the node while its right subtree contains only values greater, enabling fast lookup, insertion, and deletion.

Overview

A binary search tree is one of the foundational data structures taught alongside linked lists and hash tables, because it demonstrates how ordering data hierarchically can make search dramatically faster than scanning a flat list. Each node stores a key, an optional value, and pointers to a left and right child. The invariant that left descendants are smaller and right descendants are larger means an in-order traversal visits nodes in sorted order, and a lookup can discard half the remaining tree at each step, similar in spirit to binary search over a sorted array. On a balanced tree, search, insertion, and deletion all run in O(log n) time, which is why understanding Big O Notation matters when reasoning about BST performance. The catch is that a plain BST is not self-balancing: inserting already-sorted data can degrade it into a linked list with O(n) operations. This is why real-world systems typically use self-balancing variants (AVL trees, red-black trees) or B-trees for on-disk indexes, which apply the same ordering principle with extra bookkeeping to keep the tree shallow. BSTs underpin many higher-level structures: ordered maps and sets in standard libraries, database indexes, and expression parsers. They're also a frequent whiteboard interview topic because implementing insert, search, delete, and traversal correctly requires careful handling of recursion and edge cases like deleting a node with two children. Because pointer-chasing through tree nodes involves scattered memory access, BSTs can be slower in practice than array-based structures for small datasets despite better asymptotic complexity — a nuance worth understanding before defaulting to a tree for every ordered-data problem.

Key Concepts

• Left-subtree-smaller, right-subtree-larger ordering invariant at every node
• O(log n) average-case search, insert, and delete on a balanced tree
• In-order traversal yields keys in sorted order
• Degrades to O(n) worst case when inserted data is already sorted (unbalanced)
• Foundation for self-balancing variants like AVL and red-black trees
• Recursive definition makes insert/search/delete naturally recursive algorithms
• Supports efficient range queries (min, max, successor, predecessor)

Use Cases

Frequently Asked Questions

Related in Programming