Binary Search Tree (BST) Data Structure
A Binary Search Tree maintains the ordering invariant that every node in the left subtree is smaller and every node in the right subtree is larger, enabling O(log n) average search, insert, and delete.
| Operation | Complexity |
|---|---|
| Access | O(log n) avg / O(n) worst |
| Search | O(log n) avg / O(n) worst |
| Insertion | O(log n) avg / O(n) worst |
| Deletion | O(log n) avg / O(n) worst |
| Space | O(n) |
Interactive Visualizer · C++ / Python / Java / JS Code
Binary Search Tree (BST)
A Binary Search Tree (BST) is a Binary Tree obeying the BST invariant: for every node u, all keys in u->left are strictly smaller than u->val, and all keys in u->right are strictly greater than u->val. This turns search, insertion, deletion, predecessor/successor, and range queries into $O(h)$ operations—$O(\log n)$ when balanced, though $O(n)$ in the worst case if skewed!
At a Glance
| Operation | Average (Balanced) | Worst Case (Skewed) |
| :--- | :---: | :---: |
| Search / Min / Max | $O(\log n)$ | $O(n)$ |
| Insert / Delete | $O(\log n)$ | $O(n)$ |
| Inorder Traversal (Sorted) | $O(n)$ | $O(n)$ |
| Auxiliary Space | $O(n)$ | $O(n)$ |
---
Key Operations & Gotchas
- Deletion Has 3 Cases:
1. Leaf node → delete directly.
2. One child → replace node with its single child.
3. Two children → copy the inorder successor (leftmost node in right subtree) into the node, then delete the successor from right.
- Common Bug When Validating a BST: Checking only
left->val < root->val < right->valis WRONG! Every node must satisfy a(minBound, maxBound)range inherited from all ancestors!
---
Practice Problems
Easy
1. Search, Insert, and Delete in a BST
Implement core BST insert, search, and 3-case erase.
Approach: Recursive BST operations following the ordering invariant. Time: $O(h)$. Space: $O(h)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
struct Node {
int val;
Node *left = nullptr, *right = nullptr;
explicit Node(int v) : val(v) {}
};
Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val < root->val) root->left = insert(root->left, val);
else if (val > root->val) root->right = insert(root->right, val);
return root;
}
Node* erase(Node* root, int val) {
if (!root) return nullptr;
if (val < root->val) root->left = erase(root->left, val);
else if (val > root->val) root->right = erase(root->right, val);
else {
if (!root->left) { Node* r = root->right; delete root; return r; }
if (!root->right) { Node* l = root->left; delete root; return l; }
Node* succ = root->right;
while (succ->left) succ = succ->left;
root->val = succ->val;
root->right = erase(root->right, succ->val);
}
return root;
}
void inorder(Node* r) { if (!r) return; inorder(r->left); std::cout << r->val << " "; inorder(r->right); }
void freeTree(Node* r) { if (!r) return; freeTree(r->left); freeTree(r->right); delete r; }
int main() {
Node* root = nullptr;
for (int x : {5, 3, 7, 2, 4, 6, 8}) root = insert(root, x);
root = erase(root, 5);
inorder(root);
std::cout << "\n"; // 2 3 4 6 7 8
freeTree(root);
return 0;
}
</details>
2. Validate a Binary Search Tree (LeetCode 98)
Check whether a binary tree is a strictly valid BST.
Approach: Pass long long lo, hi bounds downward; every node must satisfy lo < node->val < hi. Time: $O(n)$. Space: $O(h)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <limits>
struct Node {
int val;
Node *left = nullptr, *right = nullptr;
explicit Node(int v) : val(v) {}
};
bool isValidBST(Node* r, long long lo = std::numeric_limits<long long>::min(),
long long hi = std::numeric_limits<long long>::max()) {
if (!r) return true;
if (r->val <= lo || r->val >= hi) return false;
return isValidBST(r->left, lo, r->val) && isValidBST(r->right, r->val, hi);
}
int main() {
Node a(5), b(1), c(6), d(4), e(7);
a.left = &b; a.right = &c; c.left = &d; c.right = &e; // 4 in right subtree of 5 -> invalid!
std::cout << std::boolalpha << isValidBST(&a) << "\n"; // false
return 0;
}
</details>
---
Intermediate
3. $k$-th Smallest Element in a BST (LeetCode 230)
Find the $k$-th smallest key in a BST (1-indexed).
Approach: Iterative inorder traversal using a stack stops immediately on the $k$-th popped node! Time: $O(h + k)$. Space: $O(h)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <stack>
struct Node {
int val;
Node *left = nullptr, *right = nullptr;
explicit Node(int v) : val(v) {}
};
int kthSmallest(Node* root, int k) {
std::stack<Node*> st;
Node* cur = root;
while (cur || !st.empty()) {
while (cur) { st.push(cur); cur = cur->left; }
cur = st.top(); st.pop();
if (--k == 0) return cur->val;
cur = cur->right;
}
return -1;
}
int main() {
Node n5(5), n3(3), n6(6), n2(2), n4(4), n1(1);
n5.left = &n3; n5.right = &n6; n3.left = &n2; n3.right = &n4; n2.left = &n1;
std::cout << kthSmallest(&n5, 3) << "\n"; // 3
return 0;
}
</details>
4. Lowest Common Ancestor in a BST (LeetCode 235)
Find the LCA of two keys p and q in a BST in $O(h)$ time and $O(1)$ space.
Approach: Walk down from root: if both p, q < cur->val, go left; if both > cur->val, go right; otherwise cur is the split point (LCA)! Time: $O(h)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
struct Node {
int val;
Node *left = nullptr, *right = nullptr;
explicit Node(int v) : val(v) {}
};
Node* lcaBST(Node* root, int p, int q) {
Node* cur = root;
while (cur) {
if (p < cur->val && q < cur->val) cur = cur->left;
else if (p > cur->val && q > cur->val) cur = cur->right;
else return cur;
}
return nullptr;
}
int main() {
Node n6(6), n2(2), n8(8), n0(0), n4(4);
n6.left = &n2; n6.right = &n8; n2.left = &n0; n2.right = &n4;
std::cout << lcaBST(&n6, 0, 4)->val << " " << lcaBST(&n6, 2, 8)->val << "\n"; // 2 6
return 0;
}
</details>
---
Hard
5. Recover a BST With Two Swapped Nodes in $O(1)$ Extra Space (LeetCode 99)
Exactly two nodes of a BST were swapped by mistake. Restore the BST without changing its structure.
Approach: Inorder traversal of a valid BST is strictly increasing. Track prev during inorder traversal: record the first and last inversion (prev->val > cur->val) into first and second, then swap first->val and second->val! Time: $O(n)$. Space: $O(h)$ (or $O(1)$ with Morris traversal).
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
struct Node {
int val;
Node *left = nullptr, *right = nullptr;
explicit Node(int v) : val(v) {}
};
void recoverTree(Node* root) {
Node *first = nullptr, *second = nullptr, *prev = nullptr;
auto inorder = [&](auto& self, Node* cur) -> void {
if (!cur) return;
self(self, cur->left);
if (prev && prev->val > cur->val) {
if (!first) first = prev;
second = cur;
}
prev = cur;
self(self, cur->right);
};
inorder(inorder, root);
if (first && second) std::swap(first->val, second->val);
}
int main() {
// Swapped 1 and 3 in BST [1, 2, 3]
Node r(1), l(3), ri(2);
r.left = &l; l.right = &ri;
recoverTree(&r);
std::cout << r.val << " " << l.val << " " << ri.val << "\n"; // 3 1 2 -> inorder: 1 2 3
return 0;
}
</details>
---
Related Structures & Algorithms
- AVL Tree & Red-Black Tree — self-balancing BSTs guaranteeing $O(\log n)$ worst-case height.
- B-Tree — multi-way balanced search tree optimized for disks and databases.