Lesson 15 of 2415 min read

Binary Search Trees

A tree with an ordering rule, which turns it into a searchable structure. Also a lesson in how a good idea degrades when the data arrives in the wrong order.

By the end: Search, insert and validate a BST, and explain why balance matters.

A binary search tree is a binary tree with one extra rule: everything in the left subtree is smaller than the node, everything in the right subtree is larger. Applied at every node, not just the root.

That rule turns a tree into a searchable structure. At each node you can discard an entire subtree, which is binary search on a tree instead of an array.

Searching a BST: each step halves the problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }

//          8
//        /   \
//       3     10
//      / \      \
//     1   6      14
//        / \     /
//       4   7   13
const bst = new TreeNode(8,
  new TreeNode(3, new TreeNode(1), new TreeNode(6, new TreeNode(4), new TreeNode(7))),
  new TreeNode(10, null, new TreeNode(14, new TreeNode(13)))
);

function search(node, target) {
  const path = [];
  while (node !== null) {
    path.push(node.val);
    if (node.val === target) return { found: true, path };
    node = target < node.val ? node.left : node.right;   // discard half
  }
  return { found: false, path };
}

console.log('find 7: ', search(bst, 7));
console.log('find 13:', search(bst, 13));
console.log('find 5: ', search(bst, 5));

Output

Finding 13 touched three nodes out of eight. On a balanced tree of a million nodes it would touch about twenty.

Inorder produces a sorted sequence

1
2
3
4
5
6
7
8class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const bst = new TreeNode(8,
  new TreeNode(3, new TreeNode(1), new TreeNode(6, new TreeNode(4), new TreeNode(7))),
  new TreeNode(10, null, new TreeNode(14, new TreeNode(13)))
);

const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };
console.log('inorder:', inorder(bst), '← sorted, for free');

Output

Insertion

Insert by walking to the empty spot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };

function insert(root, value) {
  if (root === null) return new TreeNode(value);       // found the empty slot
  if (value < root.val) root.left = insert(root.left, value);
  else if (value > root.val) root.right = insert(root.right, value);
  // equal: ignore, this BST holds no duplicates
  return root;
}

let tree = null;
for (const v of [8, 3, 10, 1, 6, 14, 4, 7, 13]) tree = insert(tree, v);
console.log('built:', inorder(tree));
console.log('root:', tree.val, '| left:', tree.left.val, '| right:', tree.right.val);

// Inserting a duplicate changes nothing.
insert(tree, 8);
console.log('after inserting 8 again:', inorder(tree));

Output

Sorted input destroys the tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
function insert(root, v) {
  if (root === null) return new TreeNode(v);
  if (v < root.val) root.left = insert(root.left, v); else if (v > root.val) root.right = insert(root.right, v);
  return root;
}
const height = (n) => n === null ? 0 : 1 + Math.max(height(n.left), height(n.right));

let balanced = null;
for (const v of [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]) balanced = insert(balanced, v);

let degenerate = null;
for (let v = 1; v <= 15; v++) degenerate = insert(degenerate, v);

console.log('15 nodes inserted in a good order → height', height(balanced), '(log2(15) is about 4)');
console.log('15 nodes inserted sorted          → height', height(degenerate), '← a linked list');

// And the search cost follows the height.
function searchSteps(node, target) { let s = 0; while (node) { s++; if (node.val === target) return s; node = target < node.val ? node.left : node.right; } return s; }
console.log('steps to find 15, balanced:  ', searchSteps(balanced, 15));
console.log('steps to find 15, degenerate:', searchSteps(degenerate, 15));

Output

Validation, and the mistake almost everyone makes

Checking that a tree is a valid BST is a classic trap. The obvious recursion — is my left child smaller and my right child larger — is wrong, because the rule applies to the whole subtree, not just the immediate children.

The wrong check, and why it passes an invalid tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }

// WRONG: only compares against immediate children.
function isValidNaive(node) {
  if (node === null) return true;
  if (node.left && node.left.val >= node.val) return false;
  if (node.right && node.right.val <= node.val) return false;
  return isValidNaive(node.left) && isValidNaive(node.right);
}

//        10
//       /  \
//      5    15
//          /  \
//         6    20     ← 6 is in the RIGHT subtree of 10 but smaller than 10
const sneaky = new TreeNode(10, new TreeNode(5), new TreeNode(15, new TreeNode(6), new TreeNode(20)));

console.log('naive check says valid:', isValidNaive(sneaky), '← but it is not');
console.log('6 sits right of 10, so every ancestor rule is broken');

Output

The correct check: carry a permitted range down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }

function isValidBST(node, low = -Infinity, high = Infinity) {
  if (node === null) return true;
  if (node.val <= low || node.val >= high) return false;
  // Going left tightens the upper bound; going right tightens the lower bound.
  return isValidBST(node.left, low, node.val) && isValidBST(node.right, node.val, high);
}

const sneaky = new TreeNode(10, new TreeNode(5), new TreeNode(15, new TreeNode(6), new TreeNode(20)));
const good = new TreeNode(10, new TreeNode(5, new TreeNode(3), new TreeNode(7)), new TreeNode(15, new TreeNode(12), new TreeNode(20)));

console.log('sneaky tree:', isValidBST(sneaky), '← correctly rejected');
console.log('good tree:  ', isValidBST(good));
console.log('single node:', isValidBST(new TreeNode(1)));
console.log('empty:      ', isValidBST(null));

// The alternative: inorder must be strictly increasing.
function isValidByInorder(root) {
  let prev = -Infinity, ok = true;
  (function walk(n) {
    if (!n || !ok) return;
    walk(n.left);
    if (n.val <= prev) ok = false;
    prev = n.val;
    walk(n.right);
  })(root);
  return ok;
}
console.log('by inorder, sneaky:', isValidByInorder(sneaky), '| good:', isValidByInorder(good));

Output

Deletion, the fiddly one

Three cases. A leaf just goes. A node with one child is replaced by that child. A node with two children is replaced by its inorder successor — the smallest value in its right subtree — which is then deleted from there.

Delete, all three cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
function insert(root, v) {
  if (root === null) return new TreeNode(v);
  if (v < root.val) root.left = insert(root.left, v); else if (v > root.val) root.right = insert(root.right, v);
  return root;
}
const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };

function minValue(node) {
  while (node.left !== null) node = node.left;
  return node.val;
}

function remove(root, value) {
  if (root === null) return null;

  if (value < root.val) { root.left = remove(root.left, value); return root; }
  if (value > root.val) { root.right = remove(root.right, value); return root; }

  // Found it. Three cases:
  if (root.left === null) return root.right;    // 0 or 1 child (right)
  if (root.right === null) return root.left;    // 1 child (left)

  // Two children: take the smallest value from the right subtree.
  const successor = minValue(root.right);
  root.val = successor;
  root.right = remove(root.right, successor);   // and remove it from there
  return root;
}

let t = null;
for (const v of [8, 3, 10, 1, 6, 14, 4, 7, 13]) t = insert(t, v);
console.log('start:            ', inorder(t));

t = remove(t, 1);
console.log('after removing 1 (leaf):        ', inorder(t));

t = remove(t, 14);
console.log('after removing 14 (one child):  ', inorder(t));

t = remove(t, 3);
console.log('after removing 3 (two children):', inorder(t));
console.log('still a valid BST (sorted):', inorder(t).every((v, i, a) => i === 0 || a[i - 1] < v));

Output

The problems BSTs are actually asked about

k-th smallest, and lowest common ancestor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const bst = new TreeNode(8,
  new TreeNode(3, new TreeNode(1), new TreeNode(6, new TreeNode(4), new TreeNode(7))),
  new TreeNode(10, null, new TreeNode(14, new TreeNode(13)))
);

// k-th smallest: inorder, stop early. O(height + k), not O(n).
function kthSmallest(root, k) {
  const stack = [];
  let node = root, seen = 0;
  while (node || stack.length) {
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop();
    if (++seen === k) return node.val;          // stop as soon as we have it
    node = node.right;
  }
  return undefined;
}

// LCA in a BST is much simpler than in a plain tree: just walk down.
function lcaBST(root, a, b) {
  let node = root;
  while (node) {
    if (a < node.val && b < node.val) node = node.left;        // both smaller
    else if (a > node.val && b > node.val) node = node.right;  // both larger
    else return node.val;                                       // they split here
  }
  return null;
}

console.log('1st smallest:', kthSmallest(bst, 1));
console.log('4th smallest:', kthSmallest(bst, 4));
console.log('8th smallest:', kthSmallest(bst, 8));
console.log('LCA of 1 and 7:  ', lcaBST(bst, 1, 7));
console.log('LCA of 13 and 14:', lcaBST(bst, 13, 14));
console.log('LCA of 1 and 13: ', lcaBST(bst, 1, 13));

Output

Build a balanced BST from a sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const height = (n) => n === null ? 0 : 1 + Math.max(height(n.left), height(n.right));
const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };

// Take the middle as the root and recurse: guarantees minimum height.
function sortedArrayToBST(nums, lo = 0, hi = nums.length - 1) {
  if (lo > hi) return null;
  const mid = Math.floor((lo + hi) / 2);
  return new TreeNode(nums[mid],
    sortedArrayToBST(nums, lo, mid - 1),
    sortedArrayToBST(nums, mid + 1, hi));
}

const sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
const balanced = sortedArrayToBST(sorted);
console.log('inorder round trip:', inorder(balanced).join(',') === sorted.join(','));
console.log('height:', height(balanced), '← minimum possible for 15 nodes');
console.log('root:', balanced.val, '| left:', balanced.left.val, '| right:', balanced.right.val);

Output

Successor, predecessor, and range queries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
const bst = new TreeNode(8,
  new TreeNode(3, new TreeNode(1), new TreeNode(6, new TreeNode(4), new TreeNode(7))),
  new TreeNode(10, null, new TreeNode(14, new TreeNode(13)))
);

// The smallest value strictly greater than target.
function successor(root, target) {
  let best = null, node = root;
  while (node) {
    if (node.val > target) { best = node.val; node = node.left; }  // candidate, try smaller
    else node = node.right;
  }
  return best;
}

// Sum of all values inside [low, high], pruning subtrees that cannot contribute.
function rangeSum(node, low, high) {
  if (node === null) return 0;
  if (node.val < low) return rangeSum(node.right, low, high);   // whole left is too small
  if (node.val > high) return rangeSum(node.left, low, high);   // whole right is too big
  return node.val + rangeSum(node.left, low, high) + rangeSum(node.right, low, high);
}

console.log('successor of 6: ', successor(bst, 6));
console.log('successor of 8: ', successor(bst, 8));
console.log('successor of 14:', successor(bst, 14));
console.log('rangeSum 7..13: ', rangeSum(bst, 7, 13), '(7+8+10+13)');
console.log('rangeSum 1..3:  ', rangeSum(bst, 1, 3), '(1+3)');

Output

When not to use one

In JavaScript, almost always. A Map gives you O(1) average lookup, which beats O(log n). A sorted array with binary search gives O(log n) lookup with far better memory locality.

A BST earns its place when you need ordered operations that a hash map cannot do: the next larger key, a range scan, the k-th smallest, or keeping data sorted under frequent insertion. If you only need lookup by exact key, use a Map.

Your turn: five BST problems

searchBST(root, val) — return the subtree rooted at the matching node, or null.
minDiffInBST(root) — the smallest difference between any two values. Inorder and compare neighbours.
closestValue(root, target) — the value closest to a given number. Walk down keeping the best.
twoSumBST(root, target) — do two values in the tree add to the target? Inorder into an array, then two pointers.
trimBST(root, low, high) — remove every node outside the range, keeping a valid BST. Recursive, with pruning.

Editable. Fill them in, then run.

class TreeNode { constructor(v, l = null, r = null) { this.val = v; this.left = l; this.right = r; } }
function insert(root, v) {
  if (root === null) return new TreeNode(v);
  if (v < root.val) root.left = insert(root.left, v); else if (v > root.val) root.right = insert(root.right, v);
  return root;
}
const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };
let bst = null;
for (const v of [8, 3, 10, 1, 6, 14, 4, 7, 13]) bst = insert(bst, v);

function searchBST(root, val) {
  // your code
}

function minDiffInBST(root) {
  // inorder, then min of consecutive differences
}

function closestValue(root, target) {
  // walk down, track the closest seen
}

function twoSumBST(root, target) {
  // inorder to array, then two pointers
}

function trimBST(root, low, high) {
  // if too small, return trim(right); if too big, return trim(left)
}

console.log(searchBST(bst, 6)?.val);              // 6
console.log(searchBST(bst, 5));                    // null
console.log(minDiffInBST(bst));                    // 1
console.log(closestValue(bst, 5));                 // 4 or 6, both are distance 1
console.log(closestValue(bst, 12));                // 13
console.log(twoSumBST(bst, 11));                   // true (4+7)
console.log(twoSumBST(bst, 100));                  // false
console.log(inorder(trimBST(bst, 4, 10)));         // [4,6,7,8,10]

Output

Recap

A BST orders every subtree, not just immediate children, which is why validation needs a range passed down rather than a local comparison.
Inorder traversal yields sorted order, and that single fact answers most BST questions.
All operations are O(height): O(log n) balanced, O(n) if built from sorted input.
Deleting a node with two children means promoting its inorder successor, the smallest value on its right.
Use a Map for plain key lookup; reach for a BST only when you need ordered operations like successor, range or k-th smallest.

Insertion

Validation, and the mistake almost everyone makes

Deletion, the fiddly one

The problems BSTs are actually asked about

When not to use one

Your turn: five BST problems

Recap

New writing, when it lands.