BST operations and ordered data

What a BST gives you that arrays and hash maps do not

A hash map answers one question very well: "is this exact key here?" A sorted array answers a second one: "what is the smallest value that is at least x?" — but only while nobody changes it, because every insert shifts everything after the insertion point. A binary search tree is the structure that tries to answer both: it keeps its values in order, so it can answer questions about order, and it changes by rewiring a few pointers, so it can keep answering them while values come and go.

The order questions are the ones a hash map cannot touch: the next larger value than x, the closest value to x, the k-th smallest, every value between a and b, the values in sorted order one at a time. This chapter is the toolkit for exactly those. It assumes the tree shape and the three traversals from Trees and the lower-bound idea from Binary search; checking that a tree is a valid BST and finding a lowest common ancestor are in Tree problems in depth and are not repeated here.

Read the last two columns together. A balanced BST is the only column with no weak row, and "plain BST, worst case" is what you get if you never rebalance. Everything in this chapter costs O(h), where h is the height of the tree — so the whole second half of it is about what keeps h small.

The node, the invariant and search

A node holds a value and two child pointers. The rule that makes it a search tree: at every node, every value in the left subtree is smaller and every value in the right subtree is larger. This chapter treats a BST as a set of distinct values. Real inputs can contain duplicates, and then you have to pick a policy and say it out loud: ignore the repeat, keep a count in the node, or always send equal values to one fixed side.

Three facts follow from the rule, and every operation below is built from them. First, in-order traversal visits the values in increasing order. Second, the smallest value is the end of the left-going path and the largest is the end of the right-going path. Third, one comparison against a node discards that node's entire left subtree or its entire right subtree — which is binary search with pointers instead of indices.

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function search(root, target) {
  let node = root;
  while (node !== null && node.val !== target) {
    node = target < node.val ? node.left : node.right; // discard one whole side
  }
  return node; // the node, or null when target is absent
}

Each step of the loop moves one level down, so the loop runs at most h + 1 times, where the height here counts the levels on the longest root-to-leaf path (a single node has height 1, the empty tree 0). That count is the cost of every operation in this chapter. It is about log2(n) for a tree with all its levels filled and n for a tree that is a chain — the same values, a completely different cost, decided only by the shape.

Helpers for the dry runs: tree to array and back

The dry runs below show a tree after every operation, so you need a compact way to write one down. This is the level-order array form that most interview platforms use: read it left to right, level by level, and write null for a missing child. The array [8,3,10,1,6,null,14] means 8 has children 3 and 10, 3 has children 1 and 6, and 10 has no left child and a right child 14. A null has no children of its own, so none are listed under it, and trailing nulls are dropped.

function buildTree(arr) {
  if (arr.length === 0 || arr[0] === null) return null;
  const root = new TreeNode(arr[0]);
  const queue = [root];
  let i = 1;
  while (i < arr.length) {
    const node = queue.shift();
    if (arr[i] !== null) {
      node.left = new TreeNode(arr[i]);
      queue.push(node.left);
    }
    i += 1;
    if (i < arr.length && arr[i] !== null) {
      node.right = new TreeNode(arr[i]);
      queue.push(node.right);
    }
    i += 1;
  }
  return root;
}

function toArray(root) {
  if (root === null) return [];
  const out = [];
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    if (node === null) {
      out.push(null);
    } else {
      out.push(node.val);
      queue.push(node.left, node.right);
    }
  }
  while (out[out.length - 1] === null) out.pop(); // trim trailing nulls
  return out;
}

function inOrder(node, out = []) {
  if (node === null) return out;
  inOrder(node.left, out);
  out.push(node.val);
  inOrder(node.right, out);
  return out;
}

queue.shift() is O(n) on a long array, which is fine for debugging helpers and not something to put inside a solution's hot loop. The Trees chapter's level-order code uses the same idiom.

Insert: walk down, hang the new node

Where does a new value belong? Search for it. The search follows the unique path the value would have to be on, and it ends by falling off the tree at a null pointer. That empty slot is the only place the value can go: any other position would put it on the wrong side of some ancestor. So insert is a search that, instead of returning null, plants a new leaf there. A new value is always a leaf, and nothing existing moves.

The recursive version uses a pattern worth learning once because delete and trim reuse it: every call returns the root of the subtree it was given, and the caller reassigns that pointer. Writing node.left = insert(node.left, val) is what links the new leaf in; at all the nodes the path passes through, the assignment just writes back the pointer that was already there.

function insert(node, val) {
  if (node === null) return new TreeNode(val); // fell off the tree: this is the slot
  if (val < node.val) node.left = insert(node.left, val);
  else if (val > node.val) node.right = insert(node.right, val);
  return node; // equal value: already present, change nothing
}

function insertIterative(root, val) {
  if (root === null) return new TreeNode(val);
  let node = root;
  while (true) {
    if (val === node.val) return root;
    if (val < node.val) {
      if (node.left === null) {
        node.left = new TreeNode(val);
        return root;
      }
      node = node.left;
    } else {
      if (node.right === null) {
        node.right = new TreeNode(val);
        return root;
      }
      node = node.right;
    }
  }
}

Both run in O(h). The recursive one uses O(h) stack; the iterative one needs O(1) extra space, which matters in JavaScript for a reason covered in the section on degenerate trees below. The tree this chapter uses from here on is the one made by inserting 8, 3, 10, 1, 6, 14, 4, 7, 13 in that order.

Dry run: building the running example

Delete: three cases

Delete is search, then repair. Finding the node is the same walk as before. What you do once you are standing on it depends on how many children it has, because the repair has to leave the in-order sequence intact minus one value.

• No children (a leaf). Nothing depends on it. Replace the pointer that led to it with null.
• One child. Replace the node with that child. The child's subtree already lies inside the range the deleted node's slot allowed, because it was a descendant of that node, so every ancestor's constraint still holds.
• Two children. Neither child can simply move up: it would have to adopt the other as a subtree. Instead, find a value that can sit in this slot without breaking anything, which means one that is at least everything on the left and at most everything on the right. There are exactly two such values: the successor (the smallest value in the right subtree) and the predecessor (the largest in the left subtree). Copy the successor's value into this node, then delete the successor from the right subtree.

The last step is not a circular definition. The successor is the leftmost node of the right subtree, so it has no left child; deleting it is always the leaf case or the one-child case.

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

function deleteNode(node, val) {
  if (node === null) return null; // value not in the tree: nothing to do
  if (val < node.val) {
    node.left = deleteNode(node.left, val);
  } else if (val > node.val) {
    node.right = deleteNode(node.right, val);
  } else {
    if (node.left === null) return node.right;  // leaf (right is null too) or only a right child
    if (node.right === null) return node.left;  // only a left child
    const heir = minNode(node.right);           // two children: the in-order successor
    node.val = heir.val;                        // copy its value up...
    node.right = deleteNode(node.right, heir.val); // ...then remove the original
  }
  return node;
}

Notice that the leaf case and the one-child case are the same two lines: a leaf has left === null, so the first return hands back node.right, which is null. Only the two-children case needs its own code. The total work is one downward path: the walk to the node, then the continued walk to the successor. That is O(h) time and O(h) stack.

Dry run: four deletions from the running example

In every row the in-order list is the previous row's list with exactly the deleted value missing. That is the invariant to check, and it is the whole proof that the repair is right: if the in-order sequence is the sorted sequence minus one value, the tree is still a BST holding the right values.

Another way: relink the node instead of copying the value

Copying heir.val into the node changes what that node object means. If anything else holds a reference to it — an iterator's stack, a map from value to node, a parent pointer table — it now silently refers to a different value. When node identity matters, move the successor node itself into the slot:

function removeMin(node) {
  if (node.left === null) return node.right;
  node.left = removeMin(node.left);
  return node;
}

function deleteRelink(node, val) {
  if (node === null) return null;
  if (val < node.val) {
    node.left = deleteRelink(node.left, val);
  } else if (val > node.val) {
    node.right = deleteRelink(node.right, val);
  } else {
    if (node.left === null) return node.right;
    if (node.right === null) return node.left;
    const heir = minNode(node.right);
    heir.right = removeMin(node.right); // detach the heir, keeping the rest of the right side
    heir.left = node.left;
    return heir;                         // the heir takes the deleted node's place
  }
  return node;
}

The order of those two assignments matters: removeMin(node.right) walks down left pointers to the heir and stops only because heir.left is still null. Assign heir.left first and, when the heir is the right child itself, the walk runs into the old left subtree and the tree breaks. Both versions produce the same shape; they differ only in which objects survive. Taking the predecessor instead of the successor also works and mirrors every line; it gives a different, equally valid tree.

Test it the cheap way

Delete is where interview BST code breaks, and a random test finds the bug in seconds. Apply the same random inserts and deletes to the tree and to a plain array, and compare in-order against the sorted array after every step. This check is complete for the BST property too: a binary tree is a valid BST exactly when its in-order sequence is strictly increasing.

function randomCheck(steps) {
  let root = null;
  let reference = [];
  for (let step = 0; step < steps; step++) {
    const value = Math.floor(Math.random() * 30);
    if (Math.random() < 0.5) {
      root = insert(root, value);
      if (!reference.includes(value)) reference.push(value);
    } else {
      root = deleteNode(root, value);
      reference = reference.filter((x) => x !== value);
    }
    const expected = [...reference].sort((a, b) => a - b);
    if (inOrder(root).join() !== expected.join()) return "mismatch after step " + step;
  }
  return "ok";
}

Successor and predecessor

The successor of a value v is the smallest value in the tree that is strictly larger than v; the predecessor is the largest that is strictly smaller. Delete just used one, and "inorder successor" is a standard question on its own. Derive it from the in-order sequence: the successor is whatever comes right after v. Two situations decide where that is.

• v has a right subtree. Everything after v in order starts inside that subtree, and the first of them is its smallest value: go right once, then left as far as possible.
• v has no right subtree. The next value is an ancestor. Climb until you arrive from a left child; that parent is the answer, because it is the first ancestor larger than v. If you never arrive from the left, v is the largest value and has no successor.

With parent pointers, those two cases are the code. Without them — the usual interview setting, where you only get the root — there is a neater single loop. Walk from the root toward v and remember the last node at which you turned left, because a left turn means that node is larger than v. If v has a right subtree, the walk continues into it, and since v is smaller than everything there it turns left all the way down, ending on the minimum of that subtree. If it has no right subtree, the remembered node is the nearest larger ancestor. Both cases fall out of one rule.

function successor(root, val) {
  let best = null;
  let node = root;
  while (node !== null) {
    if (val < node.val) {
      best = node;      // a candidate: larger than val, and we may find a smaller one
      node = node.left;
    } else {
      node = node.right; // node.val <= val: it and its left side are too small
    }
  }
  return best;
}

function predecessor(root, val) {
  let best = null;
  let node = root;
  while (node !== null) {
    if (val > node.val) {
      best = node;
      node = node.right;
    } else {
      node = node.left;
    }
  }
  return best;
}

function successorWithParent(node) { // each node has a .parent pointer, null at the root
  if (node.right !== null) return minNode(node.right);
  let child = node;
  let parent = node.parent;
  while (parent !== null && parent.right === child) {
    child = parent;
    parent = parent.parent;
  }
  return parent;
}

successor works whether or not val is in the tree: the question "what is the smallest value above 5?" is a fine one even if 5 is absent.

Dry run: successor on the running example

Cost: one downward walk, O(h) time and O(1) space. It also lets you step through a BST in order with no stack: start at the smallest value and call successor repeatedly. That costs O(h) per step, which is worse than the iterator below, but needs no stored state.

Floor and ceiling

Successor asks for the next value strictly above. Often the question allows equality: "the closest value that does not exceed 5" is 5 itself if 5 is present. Ordered-set libraries name the four relatives like this:

They are all one walk. Compare x with the current node, keep the best candidate seen so far, and descend toward where a better one could still be. For the ceiling: when the node is at least x it is a candidate, and a smaller candidate could only be on its left; when the node is below x, it and its whole left side are too small, so go right. The floor is the mirror image.

function floor(root, x) {
  let best = null;
  let node = root;
  while (node !== null) {
    if (node.val === x) return node;       // exact match: nothing can beat it
    if (node.val < x) {
      best = node;                          // fits (not above x); a larger fit could be on the right
      node = node.right;
    } else {
      node = node.left;
    }
  }
  return best;
}

function ceiling(root, x) {
  let best = null;
  let node = root;
  while (node !== null) {
    if (node.val === x) return node;
    if (node.val > x) {
      best = node;                          // fits (not below x); a smaller fit could be on the left
      node = node.left;
    } else {
      node = node.right;
    }
  }
  return best;
}

Dry run: floor and ceiling on the running example

Closest value to a target is the floor and the ceiling compared by distance: take the nearer, and decide in advance which side wins a tie. Both runs are O(h) time and O(1) space.

Kth smallest, and rank when the tree changes

In-order traversal visits values in increasing order, so the k-th smallest is the k-th node visited. You do not need to visit the rest. Use the iterative traversal from the Trees chapter, count as you pop, and stop at k. That costs O(h) to reach the first node and O(k) more to walk to the k-th, so O(h + k) time, and O(h) space for the stack.

function kthSmallest(root, k) { // k counts from 1
  const stack = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    k -= 1;
    if (k === 0) return node.val;
    node = node.right;
  }
  return undefined; // k was larger than the number of values
}

Dry run: kthSmallest(root, 3) on the running example

That is right if the tree is queried once. Now suppose the problem says the tree is modified often and k-th is asked often: "what is the 4th smallest after each insert?" Paying O(h + k) per query is no longer good enough for large k. The fix is to store in every node how many values live in its subtree. Then at a node, the left subtree's size tells you in O(1) which side holds the k-th value: if k is within the left count, go left; if k is one past it, this node is the answer; otherwise skip the left subtree and this node, subtract their count from k, and go right. One root-to-leaf walk, O(h).

class SizedNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
    this.size = 1; // how many values are in the subtree rooted here
  }
}

const sizeOf = (node) => (node === null ? 0 : node.size);

function insertSized(node, val) {
  if (node === null) return new SizedNode(val);
  if (val < node.val) node.left = insertSized(node.left, val);
  else if (val > node.val) node.right = insertSized(node.right, val);
  else return node; // duplicate: no size changes
  node.size = 1 + sizeOf(node.left) + sizeOf(node.right); // recompute on the way back up
  return node;
}

function kthBySize(root, k) {
  let node = root;
  while (node !== null) {
    const leftCount = sizeOf(node.left);
    if (k <= leftCount) {
      node = node.left;
    } else if (k === leftCount + 1) {
      return node.val;
    } else {
      k -= leftCount + 1; // skip the left subtree and this node
      node = node.right;
    }
  }
  return undefined;
}

function rank(root, x) { // how many stored values are smaller than x
  let smaller = 0;
  let node = root;
  while (node !== null) {
    if (x <= node.val) {
      node = node.left;
    } else {
      smaller += 1 + sizeOf(node.left); // this node and its whole left side are below x
      node = node.right;
    }
  }
  return smaller;
}

rank is the inverse of kthBySize — "how many values are smaller?" is the position x would take in sorted order, the same number lowerBound returns on an array. Deleting from a tree with sizes works the same way: the recursion that rewires pointers also recomputes size on the way back up, for the O(h) nodes on the path. Sizes are the simplest case of augmenting a tree: storing one extra fact per node that can be recomputed from the children. Order-statistic trees and interval trees are built on the same idea.

Dry run: kthBySize(5) and rank(7) on the running example

The subtree sizes in the example are 8 → 9, 3 → 5, 10 → 3, 6 → 3, 14 → 2, and 1, 4, 7, 13 → 1 each.

The BST iterator with an explicit stack

The task: build an object over a BST with next(), which returns the next value in increasing order, and hasNext(). The easy answer runs an in-order traversal in the constructor and stores everything in an array. That works, but the constructor costs O(n) time and O(n) memory before the first value is even requested, which is the exact thing the problem is asking you to avoid. The expected answer keeps O(h) memory and O(1) amortized time per call.

Think of the recursive in-order traversal as a process you can pause. At any moment the only state it holds is the chain of ancestors it will return to: nodes whose left subtree it is inside of, waiting to be visited themselves. That chain is the left spine from the root down to the current position, and it is exactly what an explicit stack stores. So keep that stack and advance it one step at a time: the next value is the node on top; after taking it, its right subtree is the next thing to explore, and you enter it by pushing its left spine.

class BSTIterator {
  constructor(root) {
    this.stack = [];
    this.pushLeftSpine(root);
  }

  pushLeftSpine(node) {
    while (node !== null) {
      this.stack.push(node);
      node = node.left;
    }
  }

  hasNext() {
    return this.stack.length > 0;
  }

  next() {
    const node = this.stack.pop();       // the smallest value not yet returned
    this.pushLeftSpine(node.right);      // what comes after it lies in its right subtree
    return node.val;
  }
}

Dry run: the iterator on the running example

The row that returns 8 is the one that trips people up. Its right child is 10, and 10 has no left child, so the left spine pushed is just 10. The nodes 14 and 13 are pushed one call later, when 10 is popped.

The cost claims, because interviewers ask. A single next() can push up to h nodes, so its worst case is O(h). But every node is pushed once and popped once over the whole traversal, so n calls cost O(n) in total: O(1) amortized per call. The stack never holds more than one root-to-node path, so the memory is O(h). Do not claim O(1) worst case per call, because it is not.

Two Sum IV: two iterators from opposite ends

Given a BST and a target k, are there two different nodes whose values add up to k? There are three reasonable answers, and the trade-off between them is the point of the question.

The third one is the two-pointer technique with the array replaced by an in-order walk from the small end and a reverse in-order walk from the big end. The reverse walk is the iterator with left and right exchanged. So make the iterator take a direction.

class BSTWalker {
  constructor(root, forward) {
    this.forward = forward;
    this.stack = [];
    this.descend(root);
  }

  descend(node) {
    while (node !== null) {
      this.stack.push(node);
      node = this.forward ? node.left : node.right; // forward chases the small side, backward the big side
    }
  }

  next() {
    const node = this.stack.pop();
    this.descend(this.forward ? node.right : node.left);
    return node.val;
  }
}

function findTarget(root, k) {
  if (root === null) return false;
  const up = new BSTWalker(root, true);    // ascending values
  const down = new BSTWalker(root, false); // descending values
  let a = up.next();
  let b = down.next();
  while (a < b) {                          // a < b also guarantees two different nodes
    const sum = a + b;
    if (sum === k) return true;
    if (sum < k) a = up.next();            // need a bigger sum: move the small end up
    else b = down.next();                  // need a smaller sum: move the big end down
  }
  return false;
}

There is no hasNext() check inside the loop and that is deliberate. While a < b, the value b still lies ahead of the ascending walker, so up.next() has something to return; the same argument covers the descending walker. The proof that the scan loses nothing is the one from the sorted two-sum problem: if the sum is too small, a cannot pair with any value at or below b, so it is finished.

Dry run: the tree [5,3,6,2,4,null,7]

Worst-case time is O(n): each walker moves forward at most n steps in total, using the amortized argument from the iterator. Space is O(h) for the two stacks. For one query the Set is simpler and perfectly fine; the two-iterator version is the answer to "now do it with O(h) extra space".

Sorted array or list to a balanced BST

Given values already in sorted order, build a BST of minimum height. The tempting solution — insert them one by one — is the worst possible: sorted input makes every new value go right of everything before it, producing a chain (the next sections measure what that costs). The sorted order is a gift, not a hazard, if you use it differently.

The root must have as many values below it as above it, as nearly as possible, so make the middle element the root. The elements before it, in order, are exactly the left subtree's values, and the ones after it are the right subtree's; both are sorted arrays again. Recurse on each half. At every node the two sides differ in size by at most one, so every subtree is as balanced as its size allows, and the height of the whole tree is the number of times n can be halved: ⌊log2 n⌋ + 1 levels.

function sortedArrayToBST(nums) {
  function build(lo, hi) { // builds from nums[lo..hi], both ends included
    if (lo > hi) return null;
    const mid = lo + Math.floor((hi - lo) / 2);
    const node = new TreeNode(nums[mid]);
    node.left = build(lo, mid - 1);
    node.right = build(mid + 1, hi);
    return node;
  }
  return build(0, nums.length - 1);
}

Pass index bounds, never nums.slice(...): a slice copies its range, so slicing at every level makes the whole build cost O(n log n) instead of O(n). With bounds it is O(n) time, one node created per value, and O(log n) recursion depth. For an even count there are two middles, and choosing the lower or the upper gives two different valid trees; neither is more correct.

Dry run: [-10, -3, 0, 5, 9]

The result is [0,-10,5,null,-3,null,9]: root 0, five values in three levels. Its in-order is the input array, as it must be.

The same problem from a sorted linked list. A list has no random access, so finding the middle by walking costs O(n) per call, O(n log n) overall. Do it the other way around: build the tree in the order a traversal would read the values. In-order means the left subtree is built first, and it consumes the first values of the list; then the node itself is the next list value; then the right subtree consumes the rest. Keep one cursor into the list, and use the counts to know each subtree's size.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function sortedListToBST(head) {
  let length = 0;
  for (let p = head; p !== null; p = p.next) length += 1;
  let cursor = head; // the next list value not yet placed in the tree

  function build(lo, hi) {
    if (lo > hi) return null;
    const mid = lo + Math.floor((hi - lo) / 2);
    const left = build(lo, mid - 1);       // must run first: it consumes the smaller values
    const node = new TreeNode(cursor.val); // the cursor is now exactly at this node's value
    cursor = cursor.next;
    node.left = left;
    node.right = build(mid + 1, hi);
    return node;
  }
  return build(0, length - 1);
}

Time O(n), recursion depth O(log n). For the list 1 → 2 → 3 → 4 → 5 → 6, the cursor hands out 1, 2, 3, 4, 5, 6 in that order, and the result is [3,1,5,null,2,4,6]: 3 at the root, 1 with a right child 2 on the left, and 5 with children 4 and 6 on the right. The same two-step recipe also rebalances a lopsided BST: in-order traversal into an array, then sortedArrayToBST, in O(n) time and O(n) space.

Use the ordering to prune: range sum and trim

Any question about the values within [low, high] can skip the parts of the tree that cannot contain them. If a node's value is below low, then the node and its whole left subtree are below low too, so look only at its right subtree. Symmetrically, a node above high sends you left.

function rangeSum(node, low, high) {
  if (node === null) return 0;
  if (node.val < low) return rangeSum(node.right, low, high);
  if (node.val > high) return rangeSum(node.left, low, high);
  return node.val + rangeSum(node.left, low, high) + rangeSum(node.right, low, high);
}

function trimBST(node, low, high) { // keep only values in [low, high]; returns the new subtree root
  if (node === null) return null;
  if (node.val < low) return trimBST(node.right, low, high);  // node and its left side are gone
  if (node.val > high) return trimBST(node.left, low, high);  // node and its right side are gone
  node.left = trimBST(node.left, low, high);
  node.right = trimBST(node.right, low, high);
  return node;
}

rangeSum visits the nodes inside the range, plus the nodes on at most two root-to-leaf paths (toward low and toward high) that sit outside it: O(h + m) for m values in range, not O(n). trimBST is the "return the subtree root and reassign" pattern from insert and delete again, and it is the best test of whether you absorbed that pattern: a trimmed tree's root may be a different node than the original root.

Dry run: trimBST on the running example with [4, 10]

Back up the recursion: 8's left child becomes 6 (3 and 1 are gone), 10's right child becomes null (14 and 13 are gone), and the result is [8,6,10,4,7]. The tree's root stayed 8 here; trim [9, 12] on the same tree and the answer's root is 10, not 8.

Degenerate trees: the cost is the height

Every operation above visits one root-to-node path, so its cost is the height of the tree. The BST property says nothing about that height. The values 1 through 7 inserted in increasing order make every node the right child of the one before it.

How bad is it in practice? Inserting the keys in random order tends to give a height well under n. These are measurements from one run of Node 24, in levels, with 20 random shuffles per size:

So random order lands at roughly twice the ideal height, which is acceptable, and sorted order is the full n, which is a disaster. The cost of the disaster is concrete. Inserting 100,000 sorted keys one at a time into an unbalanced BST walks about n²/2 = 5·10⁹ nodes in total; the same iterative insert as above took roughly 13 seconds on one machine running Node 24, against about 0.14 seconds for 10,000 sorted keys. A hidden test with n = 10⁵ and sorted input is the classic way a correct-looking BST solution times out.

Balanced trees in concept: rotations and AVL

A self-balancing BST repairs its own shape after each insert or delete so that the height stays O(log n) whatever order the operations arrive in. The repairs use one tool: a rotation, a local rewiring of three pointers that changes the shape without changing the in-order sequence. Since the in-order sequence is what makes a BST a BST, a rotation can never break the ordering. It only moves a node up and its neighbour down.

Take a node x whose right child is y. A left rotation at x makes y the parent and x its left child. The one subtree that is in the way is y's old left subtree B: it held values between x and y, and after the rotation it hangs from x's right side, which is precisely the range between them. Nothing else moves.

class AvlNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
    this.height = 1; // levels on the longest path down, counting this node
  }
}

const heightOf = (node) => (node === null ? 0 : node.height);

function refresh(node) {
  node.height = 1 + Math.max(heightOf(node.left), heightOf(node.right));
}

function rotateLeft(x) {
  const y = x.right;
  x.right = y.left; // the subtree between x and y changes sides
  y.left = x;
  refresh(x);       // x is now below y: update it first
  refresh(y);
  return y;         // y is the new root of this piece
}

function rotateRight(y) {
  const x = y.left;
  y.left = x.right;
  x.right = y;
  refresh(y);
  refresh(x);
  return x;
}

The AVL tree is the first self-balancing BST. Its rule: at every node, the heights of the two subtrees differ by at most 1. Each node stores its height, and after an insert or delete you recompute heights back up the path to the root. If a node's balance, height(left) − height(right), becomes +2 or −2, that node is repaired. There are four cases, named for where the extra weight sits:

The two "zig-zag" cases need two rotations because one rotation alone just moves the heavy side from one place to another: the inner grandchild is the one that is too deep, and the first rotation turns the zig-zag into a straight line so the second can fix it.

function rebalance(node) {
  refresh(node);
  const balance = heightOf(node.left) - heightOf(node.right);
  if (balance > 1) {                                       // left side too deep
    if (heightOf(node.left.left) < heightOf(node.left.right)) {
      node.left = rotateLeft(node.left);                   // left-right: straighten the zig-zag first
    }
    return rotateRight(node);
  }
  if (balance < -1) {                                      // right side too deep
    if (heightOf(node.right.right) < heightOf(node.right.left)) {
      node.right = rotateRight(node.right);                // right-left
    }
    return rotateLeft(node);
  }
  return node;
}

function avlInsert(node, val) {
  if (node === null) return new AvlNode(val);
  if (val < node.val) node.left = avlInsert(node.left, val);
  else if (val > node.val) node.right = avlInsert(node.right, val);
  else return node;
  return rebalance(node); // every node on the way back up gets checked
}

function avlDelete(node, val) { // the same three-case delete, with a rebalance on the way up
  if (node === null) return null;
  if (val < node.val) {
    node.left = avlDelete(node.left, val);
  } else if (val > node.val) {
    node.right = avlDelete(node.right, val);
  } else {
    if (node.left === null) return node.right;
    if (node.right === null) return node.left;
    const heir = minNode(node.right);
    node.val = heir.val;
    node.right = avlDelete(node.right, heir.val);
  }
  return rebalance(node);
}

Look at how little is new. avlInsert is insert with one extra line, and avlDelete is deleteNode with one extra line; the entire balancing story is inside rebalance. Everything on the path from the changed spot back to the root is revisited by the recursion's returns, which is exactly where heights go stale.

Dry run: inserting 1 through 7 into an AVL tree

A plain BST turns this input into a chain of height 7. The AVL version, with the repair at each step:

The final tree is the perfect one from the figure above: three levels, not seven. Two properties are worth knowing. An insert needs at most one repair (a single or a double rotation) to restore balance, whereas a delete can need a repair at several levels on its way up.

Why the height is logarithmic. Let N(h) be the fewest nodes an AVL tree of height h can have. Its root has one subtree of height h − 1 and, to be as thin as possible, the other of height h − 2, so N(h) = N(h − 1) + N(h − 2) + 1. That is the Fibonacci recurrence, and it grows exponentially:

Exponential growth in h means h is logarithmic in n; working it through, an AVL tree with n nodes has height at most about 1.44 × log2 n. Each rotation is a handful of pointer writes, so insert and delete are O(log n) time even in the worst case, at the cost of one extra number per node.

Red-black trees: the idea, and why you will not write one

The other balanced tree you will hear about is the red-black tree. It gets its balance from a colouring rule instead of heights. Each node is red or black, with four rules:

• The root is black.
• A red node never has a red child.
• Every path from a node down to a missing child passes through the same number of black nodes.
• Every missing child counts as black.

Those rules squeeze the tree into a bounded shape. The shortest root-to-leaf path can be all black; the longest can alternate black and red, but cannot contain more red nodes than black ones, so no path is more than about twice as long as another. That yields a height of at most 2 × log2(n + 1). A new value goes in as a red leaf, which can only violate the "no red child under red" rule; the repair recolours some nodes and does at most a constant number of rotations. Deletion is the harder half and has a longer case list.

How the two compare: an AVL tree is kept more tightly balanced, so lookups tend to be a little faster; a red-black tree does fewer rotations per update. Both give O(log n) for search, insert and delete. Java's TreeMap is documented as a red-black tree, and TreeSet is built on it; ordered containers in other standard libraries commonly are red-black trees too. Two other ways to get the same guarantee are worth a name: a treap keeps a random priority in each node and rotates to keep a heap order on the priorities, which makes the tree balanced with high probability, and a skip list reaches O(log n) expected time with layered linked lists and no rotations at all. Databases and file systems use B-trees, which put many keys in each node so a single disk read covers a lot of the search.

JavaScript has no ordered set: what to use instead

In Java you would write TreeMap or TreeSet and move on; those give floor, ceiling, k-th-style navigation and sorted iteration in O(log n). The ECMAScript standard has no equivalent. Map and Set are hash tables that iterate in insertion order, not key order; new Set([3, 1, 2]) iterates 3, 1, 2. They have no floor, no ceiling, no first or last, and no rank. Sorting their keys on every query costs O(n log n) each time.

What you do instead depends on which queries you need and how the data arrives:

The sorted array is the pragmatic default, and it is better than it sounds: the O(n) shift is real, but its constant is small. In a measurement on one machine with Node 24, 10,000 random inserts into a sorted array took about 6 ms and 100,000 took about 0.6 s — quadratic growth, from a small constant. That is plenty for the sizes most interview problems use, and you must still say that the insert is O(n) and why you accept it. Notice that it also answers rank and k-th in O(1) once you have the index, which the tree needs extra bookkeeping for.

class SortedList {
  constructor() {
    this.items = [];
  }

  lowerBound(x) { // first index whose value is >= x
    let lo = 0;
    let hi = this.items.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.items[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  upperBound(x) { // first index whose value is > x
    let lo = 0;
    let hi = this.items.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (this.items[mid] <= x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  has(x) {
    return this.items[this.lowerBound(x)] === x;
  }

  add(x) {
    const i = this.lowerBound(x);
    if (this.items[i] === x) return false;
    this.items.splice(i, 0, x); // O(n): shifts everything after i
    return true;
  }

  remove(x) {
    const i = this.lowerBound(x);
    if (this.items[i] !== x) return false;
    this.items.splice(i, 1);
    return true;
  }

  floor(x) {
    return this.items[this.upperBound(x) - 1]; // undefined if nothing is <= x
  }

  ceiling(x) {
    return this.items[this.lowerBound(x)];     // undefined if nothing is >= x
  }

  rank(x) {
    return this.lowerBound(x);                 // how many values are smaller than x
  }

  kth(k) {
    return this.items[k - 1];                  // k counts from 1
  }
}

lowerBound is the same function as in the Binary search chapter, including the hi = items.length that makes "not found" return the length. Walk through four add calls: adding 5, 1, 9 and 3 leaves items as [5], then [1,5], then [1,5,9], then [1,3,5,9]. Then floor(4) is 3, ceiling(4) is 5, rank(5) is 2 (the values 1 and 3 are smaller), and kth(3) is 5. Because it uses < directly it works for numbers and for plain strings; for pairs or objects, replace the comparison with a comparator. Do not store undefined as a value, since it is also the "not found" answer.

Recognizing it in an unseen problem

Two relatives belong to other chapters: checking that a tree is a valid BST and the lowest common ancestor in a BST are in Tree problems in depth. And a problem that merely mentions order is not automatically a BST problem. A running median wants two heaps; "count smaller numbers after self" wants merge sort or a Fenwick tree; a plain "have I seen this value?" wants a Set. Reach for a BST, or its stand-in, when the question needs the order and the data changes between questions.