Binary Search Trees (BST)

Chapter 11 · Part 3: TREES · Est. 21 min read

Chapter Goal: Master the BST invariant and every operation that flows from it — search, insert, delete, validation, order statistics, and successor/ predecessor queries. The BST is the foundation for std::set, std::map, and a huge family of interview problems that hinge on sorted order + O(log n) access.

11.1 BST Properties & Invariants

The BST Invariant

For every node N in a valid BST:

Every node in N's left subtree has a value strictly less than N.val
Every node in N's right subtree has a value strictly greater than N.val
Both left and right subtrees are themselves valid BSTs

Valid BST:              Invalid BST (6 is in wrong subtree):
       5                        5
      / \                      / \
     3   7                    3   7
    / \ / \                  / \ / \
   2  4 6  8                2  4 8  6   ← 6 < 7, must be LEFT of 7

What the Invariant Buys You

Operation	Unsorted Array	Sorted Array	BST (balanced)
Search	O(n)	O(log n)	O(log n)
Insert	O(1)	O(n) shift	O(log n)
Delete	O(n)	O(n) shift	O(log n)
Min/Max	O(n)	O(1)	O(log n)
Successor	O(n)	O(1)	O(log n)
Sorted output	O(n log n) sort	O(n)	O(n) inorder

The Critical Invariant Extension

The BST property applies to the entire subtree, not just immediate children. A common mistake is checking only parent–child relationships.

// ❌ Wrong: only checks immediate parent-child
bool isBSTWrong(TreeNode* node) {
    if (!node) return true;
    if (node->left  && node->left->val  >= node->val) return false;
    if (node->right && node->right->val <= node->val) return false;
    return isBSTWrong(node->left) && isBSTWrong(node->right);
}
 
// This fails on:    5
//                  / \
//                 1   4      ← 4 < 5 ✓ locally but 3 is in right subtree of 5
//                    / \
//                   3   6    ← 3 should NOT be in right subtree of 5!

11.2 Search, Insert & Delete

Search — Recursive & Iterative

// Recursive search: O(h) time, O(h) space (call stack)
TreeNode* search(TreeNode* root, int val) {
    if (!root || root->val == val) return root;
    if (val < root->val) return search(root->left,  val);
    else                 return search(root->right, val);
}
 
// Iterative search: O(h) time, O(1) space — preferred in interviews
TreeNode* searchIterative(TreeNode* root, int val) {
    while (root && root->val != val) {
        root = (val < root->val) ? root->left : root->right;
    }
    return root;   // nullptr if not found
}

Insert — Always at a Leaf

// Recursive insert: returns new root (handles empty tree case cleanly)
TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);  // Found insertion point
    if (val < root->val) root->left  = insert(root->left,  val);
    else if (val > root->val) root->right = insert(root->right, val);
    // If val == root->val: duplicate — do nothing (or handle as needed)
    return root;
}
 
// Iterative insert: O(h) time, O(1) space
TreeNode* insertIterative(TreeNode* root, int val) {
    TreeNode* newNode = new TreeNode(val);
    if (!root) return newNode;
 
    TreeNode* curr = root, *parent = nullptr;
    while (curr) {
        parent = curr;
        if      (val < curr->val) curr = curr->left;
        else if (val > curr->val) curr = curr->right;
        else return root;   // Duplicate — no insert
    }
    if (val < parent->val) parent->left  = newNode;
    else                   parent->right = newNode;
    return root;
}

Delete — The Three Cases

BST deletion has three cases based on the node's child count:

Case 1: Node has NO children (leaf) → simply remove it
Case 2: Node has ONE child           → replace node with its child
Case 3: Node has TWO children        → replace node's value with its
                                       inorder successor (leftmost in right subtree),
                                       then delete the successor

// Find the minimum node in a subtree (leftmost node)
TreeNode* findMin(TreeNode* node) {
    while (node->left) node = node->left;
    return node;
}
 
// Recursive delete: O(h) time
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
 
    if (key < root->val) {
        root->left  = deleteNode(root->left,  key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // Found the node to delete
        if (!root->left)  return root->right;  // Case 1 or 2 (no left child)
        if (!root->right) return root->left;   // Case 2 (no right child)
 
        // Case 3: two children
        // Find inorder successor (minimum of right subtree)
        TreeNode* successor = findMin(root->right);
        root->val = successor->val;                          // Replace value
        root->right = deleteNode(root->right, successor->val); // Delete successor
    }
    return root;
}
// Time: O(h), Space: O(h) — h = height = O(log n) balanced, O(n) worst case
 
/*
  Delete 3 from:     5         Step 1: 3 found
                    / \         Step 2: successor = leftmost of right(4) = 4
                   3   7         Step 3: replace 3 with 4
                  / \                    5
                 2   4                  / \
                                       4   7
                                      /
                                     2
*/

Finding Min and Max

// Min: go as far LEFT as possible
int findMin(TreeNode* root) {
    while (root->left) root = root->left;
    return root->val;
}
 
// Max: go as far RIGHT as possible
int findMax(TreeNode* root) {
    while (root->right) root = root->right;
    return root->val;
}
// Time: O(h), Space: O(1)

11.3 Inorder Traversal = Sorted Order

The single most important BST property: inorder traversal of a valid BST always produces elements in strictly ascending order.

// Collect all BST values in sorted order
void inorder(TreeNode* root, vector<int>& sorted) {
    if (!root) return;
    inorder(root->left, sorted);
    sorted.push_back(root->val);
    inorder(root->right, sorted);
}
 
// Verify using the property: each value should be greater than the previous
bool isBSTInorder(TreeNode* root) {
    TreeNode* prev = nullptr;
    function<bool(TreeNode*)> check = [&](TreeNode* node) -> bool {
        if (!node) return true;
        if (!check(node->left)) return false;
        if (prev && prev->val >= node->val) return false;  // Not strictly increasing
        prev = node;
        return check(node->right);
    };
    return check(root);
}

Recover BST — Two Swapped Nodes (LC 99)

If exactly two nodes are swapped, inorder traversal will reveal exactly one or two inversions. The first node of the first inversion and the second node of the last inversion are the swapped pair.

void recoverTree(TreeNode* root) {
    TreeNode* first  = nullptr;   // First wrong node
    TreeNode* second = nullptr;   // Second wrong node
    TreeNode* prev   = nullptr;   // Previous inorder node
 
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node) return;
        inorder(node->left);
 
        if (prev && prev->val > node->val) {
            if (!first) first = prev;     // First inversion: mark prev
            second = node;                // Always update second to current
        }
        prev = node;
 
        inorder(node->right);
    };
 
    inorder(root);
    swap(first->val, second->val);
}
// Time: O(n), Space: O(h)

11.4 Validating a BST

Correct Approach — Range Validation

Pass down the valid range [min, max] for each node. A node is valid only if min < node->val < max.

bool isValidBST(TreeNode* root) {
    function<bool(TreeNode*, long long, long long)> validate =
        [&](TreeNode* node, long long minVal, long long maxVal) -> bool {
        if (!node) return true;
        if (node->val <= minVal || node->val >= maxVal) return false;
        return validate(node->left,  minVal,      node->val)
            && validate(node->right, node->val,   maxVal);
    };
    return validate(root, LLONG_MIN, LLONG_MAX);
}
// Time: O(n), Space: O(h)
// Use LLONG_MIN/MAX to handle INT_MIN/INT_MAX node values
 
/*
  At root(5):   range (-inf, +inf)  → 5 valid
  At node(3):   range (-inf, 5)     → 3 valid
  At node(2):   range (-inf, 3)     → 2 valid ✓
  At node(4):   range (3, 5)        → 4 valid ✓
  At node(7):   range (5, +inf)     → 7 valid
  At node(6):   range (5, 7)        → 6 valid ✓
  At node(8):   range (7, +inf)     → 8 valid ✓
  → Valid BST ✓
*/

Alternative: Inorder + Monotone Check

bool isValidBST(TreeNode* root) {
    long long prev = LLONG_MIN;
    function<bool(TreeNode*)> inorder = [&](TreeNode* node) -> bool {
        if (!node) return true;
        if (!inorder(node->left)) return false;
        if (node->val <= prev) return false;   // Not strictly increasing
        prev = node->val;
        return inorder(node->right);
    };
    return inorder(root);
}
// Time: O(n), Space: O(h)

11.5 Successor, Predecessor & Kth Element

Inorder Successor

The inorder successor of node N is the smallest value greater than N.val.

Case 1: If N has a right subtree → successor = leftmost node in right subtree
Case 2: No right subtree         → successor = lowest ancestor for which N is
                                   in the LEFT subtree (walk up until we turn right)

// In a BST (given root, find successor of target node)
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    TreeNode* successor = nullptr;
    while (root) {
        if (p->val < root->val) {
            successor = root;        // Potential successor (we went left)
            root = root->left;
        } else {
            root = root->right;      // p is in right subtree, go right
        }
    }
    return successor;
}
// Time: O(h), Space: O(1)

Inorder Predecessor

The inorder predecessor of node N is the largest value less than N.val.

TreeNode* inorderPredecessor(TreeNode* root, TreeNode* p) {
    TreeNode* predecessor = nullptr;
    while (root) {
        if (p->val > root->val) {
            predecessor = root;      // Potential predecessor (we went right)
            root = root->right;
        } else {
            root = root->left;
        }
    }
    return predecessor;
}
// Time: O(h), Space: O(1)

Kth Smallest Element (LC 230)

Use inorder traversal — counting as we go. Stop when we've visited k nodes.

// Approach 1: Collect inorder and return k-th element — O(n) space
int kthSmallest(TreeNode* root, int k) {
    int count = 0;
    int result = -1;
 
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node || count >= k) return;
        inorder(node->left);
        if (++count == k) { result = node->val; return; }
        inorder(node->right);
    };
 
    inorder(root);
    return result;
}
// Time: O(h + k) — traverse at most h + k nodes
// Space: O(h) — recursion stack
 
// Approach 2: Iterative inorder (O(1) extra space beyond stack)
int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
 
    while (curr || !st.empty()) {
        while (curr) { st.push(curr); curr = curr->left; }
        curr = st.top(); st.pop();
        if (--k == 0) return curr->val;
        curr = curr->right;
    }
    return -1;
}

Kth Largest Element

// Reverse inorder (Right → Root → Left) visits nodes in DESCENDING order
int kthLargest(TreeNode* root, int k) {
    int count = 0, result = -1;
    function<void(TreeNode*)> reverseInorder = [&](TreeNode* node) {
        if (!node || count >= k) return;
        reverseInorder(node->right);           // Go right first
        if (++count == k) { result = node->val; return; }
        reverseInorder(node->left);
    };
    reverseInorder(root);
    return result;
}

11.6 Balanced vs. Unbalanced BST

The Height Problem

A BST's performance depends entirely on its height. Insertion in sorted order produces the worst-case degenerate (skewed) tree:

Inserting 1, 2, 3, 4, 5 in order:
1
 \
  2
   \
    3
     \
      4
       \
        5
Height = n-1 = 4.  All operations: O(n) — no better than a linked list!

Self-Balancing BSTs

Self-balancing BSTs maintain O(log n) height automatically.

Structure	Balance Condition	Height	Used In
AVL Tree		left_height - right_height	≤ 1 at every node
Red-Black Tree	No path is 2× longer than any other; root is black	O(log n)	std::set, std::map (GCC), Java TreeMap
B-Tree	All leaves at same depth	O(log n)	Databases, file systems

Interview note: You will almost never be asked to implement a Red-Black tree from scratch. You WILL be asked to use std::set/std::map (which are Red-Black Trees internally) and explain their O(log n) guarantees.

Checking Balance (From Chapter 10)

bool isBalanced(TreeNode* root) {
    function<int(TreeNode*)> checkH = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int l = checkH(node->left);  if (l == -1) return -1;
        int r = checkH(node->right); if (r == -1) return -1;
        return abs(l - r) > 1 ? -1 : 1 + max(l, r);
    };
    return checkH(root) != -1;
}

Converting Sorted Array to Balanced BST (LC 108)

TreeNode* sortedArrayToBST(vector<int>& nums) {
    function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
        if (lo > hi) return nullptr;
        int mid = lo + (hi - lo) / 2;           // Choose middle as root
        TreeNode* node = new TreeNode(nums[mid]);
        node->left  = build(lo,     mid - 1);
        node->right = build(mid + 1, hi);
        return node;
    };
    return build(0, nums.size() - 1);
}
// Time: O(n), Space: O(log n)
// Always pick the MIDDLE element to guarantee balance at every level

Converting Sorted Linked List to Balanced BST (LC 109)

TreeNode* sortedListToBST(ListNode* head) {
    if (!head) return nullptr;
    if (!head->next) return new TreeNode(head->val);
 
    // Find middle using fast/slow pointer
    ListNode* slow = head, *fast = head, *prev = nullptr;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    prev->next = nullptr;   // Split list at middle
 
    TreeNode* node  = new TreeNode(slow->val);
    node->left  = sortedListToBST(head);         // Left half
    node->right = sortedListToBST(slow->next);   // Right half
    return node;
}
// Time: O(n log n) — each level does O(n) total work to find middles

11.7 Augmented BST — Order Statistics Tree

An Order Statistics Tree augments each node with a size field — the count of nodes in its subtree. This enables O(log n) rank (position in sorted order) and select (kth element) queries.

struct OSTNode {
    int val, size;    // size = count of nodes in subtree rooted here
    OSTNode* left;
    OSTNode* right;
    OSTNode(int v) : val(v), size(1), left(nullptr), right(nullptr) {}
};
 
int getSize(OSTNode* node) { return node ? node->size : 0; }
 
void updateSize(OSTNode* node) {
    if (node) node->size = 1 + getSize(node->left) + getSize(node->right);
}
 
// Select: find the kth smallest (1-indexed)
OSTNode* select(OSTNode* root, int k) {
    if (!root) return nullptr;
    int leftSize = getSize(root->left);
 
    if      (k <= leftSize)          return select(root->left,  k);
    else if (k == leftSize + 1)      return root;               // Root is kth
    else                             return select(root->right, k - leftSize - 1);
}
// Time: O(h), Space: O(h)
 
// Rank: find how many elements are < val (rank of val in sorted order)
int rank(OSTNode* root, int val) {
    if (!root) return 0;
    if      (val < root->val) return rank(root->left, val);
    else if (val > root->val) return 1 + getSize(root->left) + rank(root->right, val);
    else                      return getSize(root->left);        // Count of nodes < val
}

In FAANG interviews, you won't implement an OST from scratch. But you WILL use std::set + order_of_key / find_by_order via GNU Policy-Based trees, or solve problems that conceptually require rank/select (often using merge sort or BIT instead).

Policy-Based Tree in C++ (GNU Extension)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;
 
ordered_set s;
s.insert(5); s.insert(2); s.insert(7); s.insert(1);
 
// order_of_key(x): number of elements strictly less than x
cout << s.order_of_key(5);   // 2  (elements: 1, 2 are less than 5)
 
// find_by_order(k): iterator to kth element (0-indexed)
cout << *s.find_by_order(0); // 1  (smallest)
cout << *s.find_by_order(2); // 5  (3rd smallest)
// Both operations: O(log n)

11.8 Sample Problems

Problem 1 — Search in a BST (Easy) — LC 700

TreeNode* searchBST(TreeNode* root, int val) {
    while (root && root->val != val)
        root = (val < root->val) ? root->left : root->right;
    return root;
}
// Time: O(h), Space: O(1)

Problem 2 — Insert into a BST (Medium) — LC 701

TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left  = insertIntoBST(root->left,  val);
    else                 root->right = insertIntoBST(root->right, val);
    return root;
}
// Time: O(h), Space: O(h)

Problem 3 — Delete Node in a BST (Medium) — LC 450

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if      (key < root->val) root->left  = deleteNode(root->left,  key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else {
        if (!root->left)  return root->right;
        if (!root->right) return root->left;
        TreeNode* succ = root->right;
        while (succ->left) succ = succ->left;
        root->val   = succ->val;
        root->right = deleteNode(root->right, succ->val);
    }
    return root;
}
// Time: O(h), Space: O(h)

Problem 4 — Validate Binary Search Tree (Medium) — LC 98

bool isValidBST(TreeNode* root) {
    function<bool(TreeNode*, long long, long long)> check =
        [&](TreeNode* node, long long lo, long long hi) -> bool {
        if (!node) return true;
        if (node->val <= lo || node->val >= hi) return false;
        return check(node->left,  lo,        node->val)
            && check(node->right, node->val, hi);
    };
    return check(root, LLONG_MIN, LLONG_MAX);
}
// Time: O(n), Space: O(h)

Problem 5 — Kth Smallest Element in a BST (Medium) — LC 230

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr || !st.empty()) {
        while (curr) { st.push(curr); curr = curr->left; }
        curr = st.top(); st.pop();
        if (--k == 0) return curr->val;
        curr = curr->right;
    }
    return -1;
}
// Time: O(h + k), Space: O(h)

Problem 6 — Lowest Common Ancestor of a BST (Easy) — LC 235

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        if      (p->val < root->val && q->val < root->val) root = root->left;
        else if (p->val > root->val && q->val > root->val) root = root->right;
        else    return root;
    }
    return nullptr;
}
// Time: O(h), Space: O(1)

Problem 7 — Convert Sorted Array to BST (Easy) — LC 108

TreeNode* sortedArrayToBST(vector<int>& nums) {
    function<TreeNode*(int,int)> build = [&](int lo, int hi) -> TreeNode* {
        if (lo > hi) return nullptr;
        int mid = lo + (hi - lo) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left  = build(lo, mid-1);
        node->right = build(mid+1, hi);
        return node;
    };
    return build(0, nums.size()-1);
}
// Time: O(n), Space: O(log n)

Problem 8 — Balance a BST (Medium) — LC 1382

Given an unbalanced BST, return a balanced BST with the same values.

TreeNode* balanceBST(TreeNode* root) {
    vector<int> inorderVals;
    function<void(TreeNode*)> collect = [&](TreeNode* node) {
        if (!node) return;
        collect(node->left);
        inorderVals.push_back(node->val);
        collect(node->right);
    };
    collect(root);   // Collect in sorted order
 
    function<TreeNode*(int,int)> build = [&](int lo, int hi) -> TreeNode* {
        if (lo > hi) return nullptr;
        int mid = lo + (hi - lo) / 2;
        TreeNode* node = new TreeNode(inorderVals[mid]);
        node->left  = build(lo, mid-1);
        node->right = build(mid+1, hi);
        return node;
    };
    return build(0, inorderVals.size()-1);
}
// Time: O(n), Space: O(n)

Problem 9 — Inorder Successor in BST (Medium) — LC 285

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    TreeNode* succ = nullptr;
    while (root) {
        if (p->val < root->val) { succ = root; root = root->left; }
        else                      root = root->right;
    }
    return succ;
}
// Time: O(h), Space: O(1)

Problem 10 — Two Sum in BST (Easy) — LC 653

Find if there exist two elements in BST that sum to target k.

bool findTarget(TreeNode* root, int k) {
    unordered_set<int> seen;
    function<bool(TreeNode*)> dfs = [&](TreeNode* node) -> bool {
        if (!node) return false;
        if (seen.count(k - node->val)) return true;
        seen.insert(node->val);
        return dfs(node->left) || dfs(node->right);
    };
    return dfs(root);
}
// Time: O(n), Space: O(n)
 
// BST-specific O(n) two-pointer approach:
// Inorder gives sorted ascending, reverse-inorder gives descending.
// Use two iterators (one forward, one backward).
bool findTargetTwoPointer(TreeNode* root, int k) {
    // Collect inorder (ascending)
    vector<int> inorder;
    function<void(TreeNode*)> collect = [&](TreeNode* node) {
        if (!node) return;
        collect(node->left);
        inorder.push_back(node->val);
        collect(node->right);
    };
    collect(root);
 
    int l = 0, r = inorder.size() - 1;
    while (l < r) {
        int sum = inorder[l] + inorder[r];
        if      (sum == k) return true;
        else if (sum  < k) l++;
        else               r--;
    }
    return false;
}

Problem 11 — Recover Binary Search Tree (Medium) — LC 99

void recoverTree(TreeNode* root) {
    TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
    function<void(TreeNode*)> inorder = [&](TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        if (prev && prev->val > node->val) {
            if (!first) first = prev;
            second = node;
        }
        prev = node;
        inorder(node->right);
    };
    inorder(root);
    swap(first->val, second->val);
}
// Time: O(n), Space: O(h)

Problem 12 — Range Sum of BST (Easy) — LC 938

Sum all values in BST in the range [low, high].

int rangeSumBST(TreeNode* root, int low, int high) {
    if (!root) return 0;
    int sum = 0;
    if (root->val >= low && root->val <= high) sum += root->val;
    // Use BST property to prune unnecessary branches
    if (root->val > low)  sum += rangeSumBST(root->left,  low, high);
    if (root->val < high) sum += rangeSumBST(root->right, low, high);
    return sum;
}
// Time: O(n) worst case, but prunes many branches in practice
// Space: O(h)

11.9 LeetCode Problem Set

#	Problem	Difficulty	Core Technique	Link
1	Validate Binary Search Tree	Medium	Range validation (lo, hi)	LC 98
2	Kth Smallest Element in a BST	Medium	Iterative inorder counting	LC 230
3	Delete Node in a BST	Medium	Three-case deletion	LC 450
4	Convert Sorted Array to BST	Easy	Mid-selection recursion	LC 108
5	Lowest Common Ancestor of BST	Easy	Split-point iteration	LC 235
6	Balance a BST	Medium	Inorder collect + rebuild	LC 1382
7	Recover Binary Search Tree	Medium	Inorder + find inversions	LC 99
8	All Elements in Two BSTs	Medium	Merge two inorder streams	LC 1305

Suggested order: #4 (Array to BST) first — it shows the mid-as-root pattern. Then #1 (Validate) with the range technique. Then #5 (LCA BST) — simplest LCA algorithm. Then #2 (Kth Smallest) and #3 (Delete). Then #6 and #7 which both leverage inorder = sorted. #8 (Merge two BSTs) is an elegant problem combining inorder traversal with merge-sorted-arrays.