DataslopeBinary Search Trees
Learn the BST invariant, search, insertion, deletion, validation, and ordered C++ containers
A binary search tree (BST) is a binary tree with an ordering invariant: every value in the left subtree is less than the root, and every value in the right subtree is greater than the root. The rule applies recursively at every node.
Sorted by structure
A BST is not necessarily sorted in memory. It is sorted by the relationship between each node and its subtrees.
Search
At each node, compare the target with the current value and choose one branch.
Insert
Insertion follows the same path as search, then attaches the new node at the first empty child position.
Min and max
The minimum is found by walking left until no left child remains. The maximum walks right.
Delete
Deletion has three cases: leaf, one child, and two children. With two children, copy the in-order successor, then delete that successor from the right subtree.
Complexity and balance
Every operation follows one root-to-leaf path, so cost is O(h), where h is height.
| Shape | Height | Operation cost |
|---|---|---|
| Balanced | O(log n) | O(log n) |
| Skewed | O(n) | O(n) |
AVL and Red-Black trees rotate nodes to stay balanced. std::set and std::map are ordered containers typically implemented as red-black trees.
In-order traversal gives sorted order
Because all left values come first, then the root, then all right values, in-order traversal of a BST yields sorted values.
Validating a BST
Checking only immediate children is wrong because a deeper node can violate an ancestor's allowed range. Correct validation carries lower and upper bounds.
Practice: Insert into BST
Implement TreeNode* insert(TreeNode* root, int val). The driver inserts values and prints in-order traversal.
Practice: Search BST
Implement bool contains(TreeNode* root, int val) using the BST ordering.
Practice: Lowest common ancestor in a BST
Implement TreeNode* lca(TreeNode* root, int a, int b). Use the BST property to walk toward the split point.
Check your understanding
What is the BST invariant for a node?
All descendants are greater than the node
Values in the left subtree are smaller and values in the right subtree are larger.
Only immediate children must be sorted alphabetically
Every node has exactly two children
What is the cost of search in a BST of height h?
O(h)
O(1) always
O(n log n)
O(n squared)
Why must BST validation track lower and upper bounds?
To count the number of nodes
To make recursion iterative
A node can satisfy its parent but violate an ancestor.
Because leaf nodes are always invalid