All Roadmaps›🧠 Data Structures & Algorithms›Phase 4›Binary Search Trees (BST) — Build, Search, Balance

Binary Search Trees (BST) — Build, Search, Balance

0/12 in this phase0/57 across the roadmap

📖 Concept

A BST is a binary tree where for every node: all values in the left subtree are less than the node, and all values in the right subtree are greater than the node.

Key operations:

Operation Average Worst (Skewed)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Min/Max O(log n) O(n)

BST property in interviews:

  • Inorder traversal gives sorted order — validate BST, find kth smallest
  • Search is binary search on a tree — go left if target < node, right if >

Deletion cases:

  1. Leaf node — just remove it
  2. One child — replace with child
  3. Two children — replace with inorder successor (or predecessor)

Balanced BSTs: AVL trees and Red-Black trees maintain O(log n) height. In interviews, you usually don't implement them but should know they exist.

🏠 Real-world analogy: A BST is like a decision tree for finding a word in a dictionary. At each page, decide: go earlier in the alphabet (left) or later (right).

💻 Code Example

codeTap to expand ⛶
1// BST — Full Implementation
2class BSTNode {
3  constructor(val) { this.val = val; this.left = null; this.right = null; }
4}
5

6class BST {
7  constructor() { this.root = null; }
8

9  insert(val) {
10    const node = new BSTNode(val);
11    if (!this.root) { this.root = node; return; }
12    let curr = this.root;
13    while (true) {
14      if (val < curr.val) {
15        if (!curr.left) { curr.left = node; return; }
16        curr = curr.left;
17      } else {
18        if (!curr.right) { curr.right = node; return; }
19        curr = curr.right;
20      }
21    }
22  }
23

24  search(val) {
25    let curr = this.root;
26    while (curr) {
27      if (val === curr.val) return curr;
28      curr = val < curr.val ? curr.left : curr.right;
29    }
30    return null;
31  }
32

33  delete(val) { this.root = this._deleteNode(this.root, val); }
34

35  _deleteNode(root, val) {
36    if (!root) return null;
37    if (val < root.val) root.left = this._deleteNode(root.left, val);
38    else if (val > root.val) root.right = this._deleteNode(root.right, val);
39    else {
40      if (!root.left) return root.right;   // Case 1 & 2
41      if (!root.right) return root.left;    // Case 2
42      // Case 3: Two children → replace with inorder successor
43      let successor = root.right;
44      while (successor.left) successor = successor.left;
45      root.val = successor.val;
46      root.right = this._deleteNode(root.right, successor.val);
47    }
48    return root;
49  }
50}
51

52// VALIDATE BST — Use range checking
53function isValidBST(root, min = -Infinity, max = Infinity) {
54  if (!root) return true;
55  if (root.val <= min || root.val >= max) return false;
56  return isValidBST(root.left, min, root.val) &&
57         isValidBST(root.right, root.val, max);
58}
59

60// KTH SMALLEST — Inorder traversal (sorted order)
61function kthSmallest(root, k) {
62  const stack = [];
63  let curr = root;
64  while (curr || stack.length) {
65    while (curr) { stack.push(curr); curr = curr.left; }
66    curr = stack.pop();
67    k--;
68    if (k === 0) return curr.val;
69    curr = curr.right;
70  }
71}
72

73// CONVERT SORTED ARRAY TO BALANCED BST
74function sortedArrayToBST(nums) {
75  function build(lo, hi) {
76    if (lo > hi) return null;
77    const mid = (lo + hi) >>> 1;
78    const node = new BSTNode(nums[mid]);
79    node.left = build(lo, mid - 1);
80    node.right = build(mid + 1, hi);
81    return node;
82  }
83  return build(0, nums.length - 1);
84}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Implement BST with insert, search, and delete
  2. Validate if a binary tree is a valid BST
  3. Find the minimum and maximum values in a BST
  4. Find the kth smallest element in a BST
  5. Convert a sorted array to a balanced BST
  6. Find the lowest common ancestor in a BST (O(log n))
  7. Delete a node from a BST (handle all 3 cases)
  8. Find the inorder successor of a node in a BST
  9. Find the closest value in a BST to a given target
  10. Construct BST from preorder traversal

⚠️ Common Mistakes

  • Validating BST by only checking parent-child relationship — must use range (min, max) for the entire subtree

  • Not handling deletion of nodes with two children — must find inorder successor/predecessor

  • Inserting duplicates without a clear policy — decide: left, right, or don't allow

  • Not recognizing that a skewed BST is essentially a linked list — all operations become O(n)

  • Confusing BST with heap — BST: left < root < right, Heap: parent >= children (max) or parent <= children (min)

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Binary Search Trees (BST) — Build, Search, Balance

← PreviousBinary Trees — Traversals & Core OperationsNext →Heaps & Priority Queues