Tracks

Full-Stack Interview Prep

Binary Search Trees

16 problems · 17 approaches

Check whether a binary tree is a BST or notMedium2 approaches

Problem

Return true if the binary tree is a valid binary search tree: every value in a node's left subtree is strictly smaller than the node, every value in its right subtree is strictly larger, and both subtrees are valid BSTs.

Example 1

Input:  [2, 1, 3]
Output: true

Example 2

Input:  [5, 1, 4, null, null, 3, 6]
Output: false

3 is in 5’s right subtree but is smaller than 5.

Also asked as: validate bst · check for BST · Check if a tree is a BST or not

1. Recurse with min/max bounds

Time O(n)Space O(h)

Every node must lie strictly between the bounds inherited from its ancestors.

function isValidBST(node, lo = -Infinity, hi = Infinity) {
  if (!node) return true;
  if (node.val <= lo || node.val >= hi) return false;
  return isValidBST(node.left, lo, node.val) && isValidBST(node.right, node.val, hi);
}

2. In-order traversal must be strictly increasing

Time O(n)Space O(h)

An in-order walk of a BST visits values in sorted order; check each value is larger than the previous.

function isValidBST(root) {
  let prev = -Infinity, ok = true;
  const dfs = (n) => {
    if (!n || !ok) return;
    dfs(n.left);
    if (n.val <= prev) ok = false;
    prev = n.val;
    dfs(n.right);
  };
  dfs(root);
  return ok;
}

BST basics — search, insert, min/maxEasy1 approach

Problem

Implement the core BST operations: search for a value, insert a value while keeping the BST property, and find the minimum and maximum values. Each takes O(h) time, where h is the tree height.

Example 1

Input:  BST [8, 3, 10, 1, 6, null, 14]: search 6, insert 7, min, max
Output: found, 7 becomes the right child of 6, 1, 14

Also asked as: Fina a value in a BST · Find min and max value in a BST

1. Follow the ordering invariant

Time O(h)Space O(1)

Go left if the target is smaller, right if larger. Min is the leftmost node, max the rightmost.

function search(root, key) {
  let n = root;
  while (n && n.val !== key) n = key < n.val ? n.left : n.right;
  return n;
}
function insert(root, key) {
  if (!root) return { val: key, left: null, right: null };
  if (key < root.val) root.left = insert(root.left, key);
  else if (key > root.val) root.right = insert(root.right, key);
  return root;
}
const findMin = (n) => { while (n.left) n = n.left; return n.val; };
const findMax = (n) => { while (n.right) n = n.right; return n.val; };

Delete a node from a BSTMedium1 approach

Problem

Delete the node with a given key from a BST and return the root, keeping the BST property. There are three cases: the node is a leaf, it has one child, or it has two children (replace it with its in-order successor or predecessor).

Example 1

Input:  root = [5, 3, 6, 2, 4, null, 7], key = 3
Output: [5, 4, 6, 2, null, null, 7]

Also asked as: Deletion of a node in a BST

1. Three cases: leaf, one child, two children

Time O(h)Space O(h)

Leaf → remove. One child → splice it in. Two children → replace the value with the in-order successor (leftmost of the right subtree), then delete that successor.

function deleteNode(root, key) {
  if (!root) return null;
  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;
    let succ = root.right;
    while (succ.left) succ = succ.left;
    root.val = succ.val;
    root.right = deleteNode(root.right, succ.val);
  }
  return root;
}

Inorder successor and predecessor in a BSTMedium1 approach

Problem

Given a BST and a key (which may or may not be in the tree), return the in-order predecessor (the largest value smaller than the key) and successor (the smallest value larger than the key).

Example 1

Input:  BST [50, 30, 70, 20, 40, 60, 80], key = 65
Output: predecessor 60, successor 70

Also asked as: Find inorder successor and inorder predecessor in a BST · Populate Inorder successor of all nodes

1. Descend, remembering the last turn

Time O(h)Space O(1)

Successor: go right and take the leftmost; if no right child, it is the last ancestor you turned left from. Predecessor is the mirror.

function inorderSuccessor(root, key) {
  let succ = null, n = root;
  while (n) {
    if (key < n.val) { succ = n; n = n.left; }
    else n = n.right;
  }
  return succ;
}
// Populate .next for every node: reverse in-order traversal, keeping a running "next".

Construct a BST from preorder / validate a preorder sequenceMedium1 approach

Problem

(1) Build the BST whose preorder traversal is the given array. (2) Given an array, return true if it could be the preorder traversal of some BST.

Example 1

Input:  build from [8, 5, 1, 7, 10, 12]
Output: [8, 5, 10, 1, 7, null, 12]

Example 2

Input:  valid? [2, 4, 1]
Output: false

Also asked as: Construct BST from preorder traversal · Check preorder is valid or not

1. Bounds recursion

Time O(n)Space O(h)

Consume preorder values while they fit the current (low, high) bound; the first value becomes the root, then recurse left with an updated upper bound and right with a lower bound.

function bstFromPreorder(preorder) {
  let i = 0;
  const build = (bound) => {
    if (i === preorder.length || preorder[i] > bound) return null;
    const node = { val: preorder[i++], left: null, right: null };
    node.left = build(node.val);
    node.right = build(bound);
    return node;
  };
  return build(Infinity);
}

Validate a preorder: use a stack; pop while the current value exceeds the stack top (that becomes the new lower bound). If any value is below the current lower bound, it is invalid.

Convert a binary tree to a BST / balance a BST / flatten a BST to a sorted listMedium1 approach

Problem

Three reshaping tasks. (1) Convert a binary tree into a BST while keeping its exact shape. (2) Turn a skewed BST into a height-balanced BST with the same values. (3) Flatten a BST into a sorted list that runs through right pointers, with every left pointer null.

Example 1

Input:  balance the skewed BST 1 → 2 → 3 → 4 (right children)
Output: [3, 2, 4, 1] or [2, 1, 3, null, null, null, 4]

Also asked as: Convert Binary tree into BST · Convert a normal BST into a Balanced BST · Flatten BST to sorted list

1. In-order array ↔ balanced BST

Time O(n)Space O(n)

Collect the in-order values (sorted for a BST). To convert a plain binary tree: sort the collected values. To balance: recursively pick the middle as the root. To flatten: rebuild as a right-only chain.

function inorderVals(n, out = []) { if (n) { inorderVals(n.left, out); out.push(n.val); inorderVals(n.right, out); } return out; }

function sortedArrayToBST(a, lo = 0, hi = a.length - 1) {
  if (lo > hi) return null;
  const mid = (lo + hi) >> 1;
  return { val: a[mid], left: sortedArrayToBST(a, lo, mid - 1), right: sortedArrayToBST(a, mid + 1, hi) };
}

function balanceBST(root) { return sortedArrayToBST(inorderVals(root)); }
function treeToBST(root) { return sortedArrayToBST(inorderVals(root).sort((x, y) => x - y)); }

function flattenToSortedList(root) {
  const a = inorderVals(root);
  const dummy = { right: null }; let t = dummy;
  for (const v of a) { t.right = { val: v, left: null, right: null }; t = t.right; }
  return dummy.right;
}

Merge two BSTsMedium1 approach

Problem

Given two BSTs, return all of their values combined in sorted order, or build a single balanced BST from them. Aim for O(m + n) time.

Example 1

Input:  BST1 = [3, 1, 5], BST2 = [4, 2, 6]
Output: [1, 2, 3, 4, 5, 6]

Also asked as: Merge two BST

1. In-order lists → merge → build balanced BST

Time O(n + m)Space O(n + m)

In-order traversal of each BST gives two sorted arrays; merge them, then build a height-balanced BST from the merged array.

function mergeBSTs(a, b) {
  const inorder = (n, out = []) => { if (n) { inorder(n.left, out); out.push(n.val); inorder(n.right, out); } return out; };
  const A = inorder(a), B = inorder(b);
  const merged = [];
  let i = 0, j = 0;
  while (i < A.length && j < B.length) merged.push(A[i] <= B[j] ? A[i++] : B[j++]);
  while (i < A.length) merged.push(A[i++]);
  while (j < B.length) merged.push(B[j++]);
  const build = (lo, hi) => lo > hi ? null : (() => { const m = (lo + hi) >> 1; return { val: merged[m], left: build(lo, m - 1), right: build(m + 1, hi) }; })();
  return build(0, merged.length - 1);
}

Kth smallest / Kth largest element in a BSTMedium1 approach

Problem

Return the kth smallest (or kth largest) value in a BST, with k counted from 1.

Example 1

Input:  root = [5, 3, 6, 2, 4, null, null, 1], k = 3
Output: kth smallest = 3

Also asked as: Find Kth smallest element in a BST · Find Kth largest element in a BST

1. Controlled in-order (reverse in-order for largest)

Time O(h + k)Space O(h)

In-order visits values ascending; stop at the kth. For kth largest, do a reverse in-order (right, node, left).

function kthSmallest(root, k) {
  const st = [];
  let cur = root;
  while (cur || st.length) {
    while (cur) { st.push(cur); cur = cur.left; }
    cur = st.pop();
    if (--k === 0) return cur.val;
    cur = cur.right;
  }
}
// kth largest: same loop with left/right swapped.

Count pairs from two BSTs whose sum equals XMedium1 approach

Problem

Count pairs (a from the first BST, b from the second) with a + b = x.

Example 1

Input:  BST1 = {1, 3, 5, 6, 7, 8, 10}, BST2 = {2, 3, 4, 5, 6, 8, 9, 11}, x = 16
Output: 3

(5, 11), (7, 9) and (8, 8).

Also asked as: Count pairs from 2 BST whose sum is equal to given value "X"

1. In-order of one, reverse in-order of the other, two pointers

Time O(n + m)Space O(h1 + h2)

Ascending stream from BST1, descending stream from BST2. Advance the streams like the two-pointer pair-sum on sorted arrays.

function countPairs(root1, root2, x) {
  const asc = [], desc = [];
  (function inL(n){ if(!n) return; inL(n.left); asc.push(n.val); inL(n.right); })(root1);
  (function inR(n){ if(!n) return; inR(n.right); desc.push(n.val); inR(n.left); })(root2);
  let i = 0, j = 0, count = 0;
  while (i < asc.length && j < desc.length) {
    const s = asc[i] + desc[j];
    if (s === x) { count++; i++; j++; }
    else if (s < x) i++;
    else j++;
  }
  return count;
}

Median of a BST in O(n) time, O(1) space / count nodes in a rangeMedium1 approach

Problem

(1) Return the median of all values in a BST using O(n) time and O(1) extra space (no recursion stack, so use Morris traversal). (2) Count the nodes whose values lie in the range [low, high].

Example 1

Input:  BST {1, 3, 4, 6, 7, 8, 9}
Output: median 6

Example 2

Input:  count in [5, 45] for BST {10, 5, 50, 1, 40, 100}
Output: 3

Also asked as: Find the median of BST in O(n) time and O(1) space · Count BST ndoes that lie in a given range

1. Morris in-order traversal (median) + pruned recursion (range count)

Time O(n)Space O(1) for median

Morris traversal walks in-order with O(1) space by temporarily threading predecessors. First pass counts n; second pass stops at position n/2. Range count: skip a subtree entirely when its root is outside [lo, hi].

function countInRange(node, lo, hi) {
  if (!node) return 0;
  if (node.val < lo) return countInRange(node.right, lo, hi);
  if (node.val > hi) return countInRange(node.left, lo, hi);
  return 1 + countInRange(node.left, lo, hi) + countInRange(node.right, lo, hi);
}

Morris median: do one Morris pass to count nodes, a second Morris pass to read the middle value(s). Threads are removed as you go, so no stack/recursion.

Replace each element with the least greater element on its rightMedium1 approach

Problem

Replace each element with the smallest element to its right that is greater than it, or −1 if none exists.

Example 1

Input:  [8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28]
Output: [18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1]

Also asked as: Replace every element with the least greater element on its right

1. Insert right-to-left into a BST, read the successor

Time O(n·h)Space O(n)

Process the array from the end. Insert each value into a BST; on the way down, the last node you turned left from is its least greater element.

function replaceWithLeastGreater(a) {
  let root = null;
  const res = Array(a.length).fill(-1);
  const insert = (val, i) => {
    let succ = null, node = root, parent = null, dir = '';
    while (node) { parent = node; if (val < node.val) { succ = node; node = node.left; dir = 'left'; } else { node = node.right; dir = 'right'; } }
    const fresh = { val, left: null, right: null };
    if (!parent) root = fresh; else parent[dir] = fresh;
    if (succ) res[i] = succ.val;
  };
  for (let i = a.length - 1; i >= 0; i--) insert(a[i], i);
  return res;
}

Find conflicting appointmentsMedium1 approach

Problem

Appointments [start, end] arrive in order. Print every appointment that overlaps with any earlier one.

Example 1

Input:  [[1,5], [3,7], [2,6], [10,15], [5,6], [4,100]]
Output: [3,7] conflicts with [1,5]; [2,6] with [1,5]; [5,6] with [3,7]; [4,100] with [1,5]

Also asked as: Given "n" appointments, find the conflicting appointments

1. Interval-BST (or sort + sweep)

Time O(n log n)Space O(n)

Insert each [start, end] into an interval tree keyed by start; on insert, any node whose range overlaps the new one is a conflict. Simpler: sort by start, and any appointment whose start < previous max end conflicts.

function conflictingAppointments(appts) {
  const sorted = [...appts].sort((a, b) => a[0] - b[0]);
  const conflicts = [];
  let maxEnd = -Infinity, prev = null;
  for (const [s, e] of sorted) {
    if (s < maxEnd) conflicts.push([[prev[0], prev[1]], [s, e]]);
    if (e > maxEnd) { maxEnd = e; prev = [s, e]; }
  }
  return conflicts;
}

Check whether a BST contains a dead endMedium1 approach

Problem

The BST holds positive integers. A dead end is a leaf where no new value can be inserted, because both value − 1 and value + 1 are already taken (treat 0 as taken). Return true if the BST contains a dead end.

Example 1

Input:  BST {8, 5, 2, 3, 7, 11, 4}
Output: true

Leaf 4: 3 and 5 are both present.

Also asked as: Check whether BST contains Dead end

1. Track the allowed (lo, hi) window; a leaf with hi − lo === 2 is a dead end

Time O(n)Space O(h)

A dead-end leaf value v can’t accept any new node because both v−1 and v+1 are boundaries. That happens exactly when the leaf’s open interval is (v−1, v+1).

function hasDeadEnd(root, lo = 1, hi = Infinity) {
  if (!root) return false;
  if (!root.left && !root.right) return root.val - lo === 1 && hi - root.val === 1;
  return hasDeadEnd(root.left, lo, root.val - 1) || hasDeadEnd(root.right, root.val + 1, hi);
}

Largest BST subtree in a binary treeHard1 approach

Problem

Return the number of nodes in the largest subtree that is itself a valid BST.

Example 1

Input:  [10, 5, 15, 1, 8, null, 7]
Output: 3

The subtree rooted at 5: {5, 1, 8}.

Also asked as: Largest BST in a Binary Tree

1. Post-order returning (isBST, size, min, max)

Time O(n)Space O(h)

A node forms a BST iff both children are BSTs and node.val > leftMax and node.val < rightMin. Track the largest size seen.

function largestBSTSubtree(root) {
  let best = 0;
  const dfs = (n) => {
    if (!n) return { isBST: true, size: 0, min: Infinity, max: -Infinity };
    const L = dfs(n.left), R = dfs(n.right);
    if (L.isBST && R.isBST && n.val > L.max && n.val < R.min) {
      const size = L.size + R.size + 1;
      best = Math.max(best, size);
      return { isBST: true, size, min: Math.min(n.val, L.min), max: Math.max(n.val, R.max) };
    }
    return { isBST: false, size: 0, min: 0, max: 0 };
  };
  dfs(root);
  return best;
}

Lowest Common Ancestor of a BSTMedium1 approach

Problem

Given a BST and two nodes p and q in it, return their lowest common ancestor (a node counts as its own descendant). Use the BST ordering instead of searching the whole tree.

Example 1

Input:  root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Example 2

Input:  same tree, p = 2, q = 4
Output: 2

1. Walk down using ordering

Time O(h)Space O(1)

Both values smaller → go left; both larger → go right; otherwise this node splits them and is the LCA.

function lowestCommonAncestor(root, p, q) {
  let node = root;
  while (node) {
    if (p.val < node.val && q.val < node.val) node = node.left;
    else if (p.val > node.val && q.val > node.val) node = node.right;
    else return node;
  }
  return null;
}

Convert Sorted Array to BSTEasy1 approach

Problem

Given a sorted array, build a height-balanced BST from it (the depths of the two subtrees of every node differ by at most 1).

Example 1

Input:  [-10, -3, 0, 5, 9]
Output: [0, -3, 9, -10, null, 5] (any balanced BST is accepted)

1. Middle as root, recurse

Time O(n)Space O(log n)

Choosing the middle element keeps both halves equal in size, giving a height-balanced tree.

function sortedArrayToBST(nums, lo = 0, hi = nums.length - 1) {
  if (lo > hi) return null;
  const mid = (lo + hi) >> 1;
  const node = new TreeNode(nums[mid]);
  node.left = sortedArrayToBST(nums, lo, mid - 1);
  node.right = sortedArrayToBST(nums, mid + 1, hi);
  return node;
}