Part 11 · Lesson 44 · read

Binary Search Trees

Search, insert, delete, check a tree is valid, and find the k-th smallest value.

The BST property

A binary search tree (BST) is a binary tree (a tree where each node has at most two children) that obeys one rule at every node. It is called "search" because the rule lets you find a value fast:

The BST property

Every value in the left side of a node (its left subtree, meaning the left child and everything below it) is smaller than the value of the node. Every value in the right side is larger. (We assume all values are different, as LeetCode does for these problems.)

Notice the word every. The rule covers the whole left side and right side, not only the direct children. This detail causes the most common bug in this lesson. Two things make BSTs useful:

Binary search on a tree. At each node you can ignore one whole side. Binary search on a sorted array (checking the middle item and throwing away the half that cannot hold the answer) works in the same way. A search takes at most as many steps as the tree is tall.
Inorder gives sorted order. Visit the left side, then the node, then the right side. This is the inorder walk (a way to visit every node of a tree) from lesson 41. It lists the values from smallest to largest. Several questions below use just this fact.

Most operations cost O(h), where h is the height of the tree (the number of levels from the root to the lowest leaf). That means the work grows with the height. For a bushy tree h is about log n. The last section shows when it is not. All samples use the same buildTree helper as the last lesson (a level-order array, with null for a missing child). Each sample is complete on its own.

Search

Compare the target with the current node. If they are equal, you found it. If the target is smaller, go left. If it is larger, go right. If you fall off the tree (null), the value is not there. Here are two versions: one with recursion and one with a loop. The loop uses O(1) extra space. The recursion uses O(h) for the call stack (the pile of open calls).

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function searchRecursive(node, target) {  if (node === null) return null;                 // fell off the tree: not present  if (target === node.val) return node;  return target < node.val    ? searchRecursive(node.left, target)          // smaller values can only be on the left    : searchRecursive(node.right, target);        // larger values can only be on the right}function searchIterative(node, target) {  while (node !== null && node.val !== target) {    node = target < node.val ? node.left : node.right;  }  return node;}const tree = buildTree([8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]);console.log(searchRecursive(tree, 6).val);   // 6console.log(searchIterative(tree, 13).val);  // 13console.log(searchIterative(tree, 5));       // null

Insert

To insert, you search, and you stop at the empty spot where the value should be. The new node always becomes a leaf (a node with no children). Existing nodes never move. The helper serialize in this sample turns a tree back into a level-order array, so we can print it.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function insertRecursive(node, val) {  if (node === null) return new TreeNode(val);      // found the empty spot: the new node is a leaf  if (val < node.val) node.left = insertRecursive(node.left, val);  else node.right = insertRecursive(node.right, val);  return node;}function insertIterative(root, val) {  const fresh = new TreeNode(val);  if (root === null) return fresh;  let cur = root;  while (true) {    if (val < cur.val) {      if (cur.left === null) { cur.left = fresh; break; }      cur = cur.left;    } else {      if (cur.right === null) { cur.right = fresh; break; }      cur = cur.right;    }  }  return root;}console.log(serialize(insertRecursive(buildTree([4, 2, 7, 1, 3]), 5))); // [4, 2, 7, 1, 3, 5]console.log(serialize(insertIterative(buildTree([4, 2, 7, 1, 3]), 6)));  // [4, 2, 7, 1, 3, 6]console.log(serialize(insertRecursive(null, 9)));                         // [9]

More than one tree can be a valid answer after an insertion. Some methods move existing nodes around (for example, methods that turn nodes around to keep the tree short). The simple "add as a leaf" method is what interviewers usually expect.

Delete: three cases

First find the node (search). Then it is in one of three situations:

Dry run · deleting a node

Case	What to do	Why it keeps the BST property
It is a leaf	Remove it (return null to the parent)	Nothing depended on it.
It has one child	Replace it with that child	The child, with everything below it, is already on the correct side of the parent.
It has two children	Copy the inorder successor (the next value in sorted order, which is the smallest value on the right side) into this node. Then delete that successor from the right side	The successor is larger than everything on the left, and not larger than anything on the right.

The successor has no left child (otherwise it would not be the smallest). So deleting it is always case 1 or 2. You can also use the largest value on the left side, the inorder predecessor (the value just before it in sorted order). It works just as well.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function deleteNode(root, key) {  if (root === null) return null;                    // key is not in the tree  if (key < root.val) {    root.left = deleteNode(root.left, key);  } else if (key > root.val) {    root.right = deleteNode(root.right, key);  } else {    // Found it. Case 1 (leaf) and case 2 (one child) both reduce to: return the child that exists.    if (root.left === null) return root.right;    if (root.right === null) return root.left;    // Case 3: two children. Copy the inorder successor (smallest value on the right) here, then delete it from the right.    let successor = root.right;    while (successor.left !== null) successor = successor.left;    root.val = successor.val;    root.right = deleteNode(root.right, successor.val);  }  return root;}console.log(serialize(deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 2))); // [5, 3, 6, null, 4, null, 7]   (leaf)console.log(serialize(deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 6))); // [5, 3, 7, 2, 4]              (one child)console.log(serialize(deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 3))); // [5, 4, 6, 2, null, null, 7]  (two children)console.log(serialize(deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 9))); // [5, 3, 6, 2, 4, null, 7]     (not found)

The function returns the root of each part of the tree (it may be a new node), so the parent can attach it again with root.left = deleteNode(root.left, key). Time is O(h): one search down, plus one more walk down to find the successor.

Validate a BST

Is this tree a valid BST? The easy idea is to check each node against its two children. It looks right, but it is wrong:

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// WRONG: only compares each node with its direct children.function isValidWrong(node) {  if (node === null) return true;  if (node.left !== null && node.left.val >= node.val) return false;  if (node.right !== null && node.right.val <= node.val) return false;  return isValidWrong(node.left) && isValidWrong(node.right);}//        5//       / \//      1   6//         / \//        3   7        3 is smaller than 5 but sits in 5's RIGHT subtreeconst bad = buildTree([5, 1, 6, null, null, 3, 7]);console.log(isValidWrong(bad)); // true   <- wrong answer, this is not a BST

Here every parent-child pair is fine (1 < 5, 6 > 5, 3 < 6, 7 > 6). But 3 is on the right side of 5, which breaks the rule for every node. The fix is to carry limits down the tree. When you go left, the current value becomes the new upper limit. When you go right, it becomes the new lower limit. Each node must be strictly between the limits set by all of its ancestors (the parent, the grandparent, and so on up to the root).

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isValidBST(root) {  // Every node must lie strictly between lo and hi, the limits set by ALL its ancestors.  function check(node, lo, hi) {    if (node === null) return true;    if (node.val <= lo || node.val >= hi) return false;    return check(node.left, lo, node.val)        // going left: this node becomes the new upper limit        && check(node.right, node.val, hi);      // going right: this node becomes the new lower limit  }  return check(root, -Infinity, Infinity);}console.log(isValidBST(buildTree([5, 1, 6, null, null, 3, 7])));  // falseconsole.log(isValidBST(buildTree([2, 1, 3])));                    // trueconsole.log(isValidBST(buildTree([2, 2, 2])));                    // false  (no duplicates allowed)

O(n) time, O(h) space. Another way to test: do an inorder walk and check that each value is strictly larger than the one before it. Use -Infinity and Infinity as the starting limits. Do not use the smallest and largest whole numbers, because a node may really hold one of those numbers.

K-th smallest with inorder

Inorder visits values from smallest to largest. So the k-th smallest value is the k-th node we visit. The version without recursion keeps its own stack (a pile where the last item added is the first one taken out) of the nodes on the way back up. This lets us stop early as soon as we have counted k nodes. We visit only about h + k nodes, not all n.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function kthSmallest(root, k) {  const stack = [];  let cur = root;  while (cur !== null || stack.length > 0) {    while (cur !== null) {          // go as far left as possible, remembering the path      stack.push(cur);      cur = cur.left;    }    cur = stack.pop();              // the smallest value not yet counted    k--;    if (k === 0) return cur.val;    // stop early: no need to visit the rest of the tree    cur = cur.right;  }  return undefined;                 // k is larger than the number of nodes}const tree = buildTree([5, 3, 6, 2, 4, null, null, 1]);console.log(kthSmallest(tree, 1)); // 1console.log(kthSmallest(tree, 3)); // 3console.log(kthSmallest(tree, 6)); // 6

Traced: the 3rd smallest value

step 1 / 15

Set up

cur = root (5), k = 3

We want the 3rd smallest value of the tree 5 → (3 → (2 → 1), 4), 6. Inorder gives values from smallest to largest, so we need the third value that we pop.

1function kthSmallest(root, k) {2  const stack = [];▶  let cur = root;4  while (cur !== null || stack.length > 0) {5    while (cur !== null) {6      stack.push(cur);7      cur = cur.left;8    }9    cur = stack.pop();10    k--;11    if (k === 0) return cur.val;12    cur = cur.right;13  }14}15console.log(kthSmallest(root, 3));

Variables

k	3
cur	5
stack	[]

Console

(nothing printed yet)

The stack always holds the ancestors that are still waiting for their turn. Each pop gives the next value in sorted order: 1, 2, then 3. · interactive

Build a balanced BST from a sorted array

If you insert values in sorted order, you get a lopsided tree (see the next section). So build the tree directly instead. Make the middle element the root. Then do the same for the left half and the right half. Each split keeps the two sides within one element of each other. So the tree is height-balanced.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function sortedArrayToBST(nums) {  function build(lo, hi) {                           // build from nums[lo..hi], both inclusive    if (lo > hi) return null;    const mid = Math.ceil((lo + hi) / 2);            // the middle value becomes the root    return new TreeNode(nums[mid], build(lo, mid - 1), build(mid + 1, hi));  }  return build(0, nums.length - 1);}console.log(serialize(sortedArrayToBST([-10, -3, 0, 5, 9]))); // [0, -3, 9, -10, null, 5]console.log(serialize(sortedArrayToBST([1, 3])));              // [3, 1]console.log(serialize(sortedArrayToBST([1, 2, 3, 4, 5, 6, 7]))); // [4, 2, 6, 1, 3, 5, 7]

O(n) time (one node per element) and O(log n) recursion depth. When the range has an even number of items, you can choose the lower middle or the upper middle. You get different trees, and both are valid.

Why an unbalanced BST is O(n)

O(h) is only as good as h. Say the values arrive in sorted order. Each new value is the largest so far, so it goes far to the right. The result is a chain where every node has just one child. That is really a linked list (items joined one after another in a single line) shaped like a tree. Search, insert and delete all become O(n). This is called a degenerate (or skewed) tree.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function insert(root, val) {  if (root === null) return new TreeNode(val);  if (val < root.val) root.left = insert(root.left, val);  else root.right = insert(root.right, val);  return root;}function height(node) {  return node === null ? 0 : 1 + Math.max(height(node.left), height(node.right));}function build(values) {  let root = null;  for (const v of values) root = insert(root, v);  return root;}const chain = build([1, 2, 3, 4, 5, 6, 7]);   // inserted in sorted orderconst bushy = build([4, 2, 6, 1, 3, 5, 7]);   // the same values, inserted middle-firstconsole.log(height(chain)); // 7   every node has only a right child: it is a linked listconsole.log(height(bushy)); // 3   a search needs at most 3 comparisons

Balanced trees exist, but you rarely write them

Self-balancing trees (AVL trees and red-black trees) turn nodes around (this is called rotating) after each insert and delete. This keeps h about log n, so every operation takes O(log n). Many language libraries use them inside ordered maps and sets (for example Java's TreeMap and C++'s std::map). In interviews it is enough to know that they exist. You can say: "O(h). That is O(log n) if the tree is balanced, and O(n) in the worst case."

In a balanced tree, each level holds about twice as many nodes as the level above. So a perfectly balanced tree with 1,000,000 nodes is only about 20 levels tall. A search needs about 20 comparisons. The degenerate version could need a million.

Practice questions

Before you code any BST question, ask two things. "Can I ignore one side because of the BST property?" And "Would inorder help?"

Q1Search in a binary search treeEasy

You get the root of a BST and an integer val. Find the node whose value equals val. Return that node with everything below it (its subtree), or null if there is none.

Example 1

Input: root = [4, 2, 7, 1, 3], val = 2

Output: [2, 1, 3]

Explanation: We return the node with value 2 together with everything below it.

Example 2

Input: root = [4, 2, 7, 1, 3], val = 5

Output: []

Explanation: 5 is not in the tree, so the answer is null (an empty tree).

Stuck? Open one hint at a time

Hint 1

You do not have to look at every node. Compare the target with the current value.

Hint 2

If the target is smaller, everything on the right is too big. If it is larger, everything on the left is too small. So you can ignore that side.

Show all 3 solutions with explanations

Approach 1Brute force: visit every node

The idea

Ignore the BST property. Search the whole tree with an ordinary DFS (depth-first search: go all the way down one branch, then back up to try the next) until you find the value.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function searchBST(root, val) {  if (root === null) return null;  if (root.val === val) return root;  return searchBST(root.left, val) ?? searchBST(root.right, val);}console.log(serialize(searchBST(buildTree([4, 2, 7, 1, 3]), 2))); // [2, 1, 3]console.log(serialize(searchBST(buildTree([4, 2, 7, 1, 3]), 5))); // []

How it works

It works on any binary tree, but it costs O(n) even when the tree is a BST.

Approach 2Recursive: go to the one side that can hold the value

The idea

If equal, return the node. If the target is smaller, search the left child. If it is larger, search the right child. null means not found.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function searchBST(root, val) {  if (root === null || root.val === val) return root;  return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);}console.log(serialize(searchBST(buildTree([4, 2, 7, 1, 3]), 2))); // [2, 1, 3]console.log(serialize(searchBST(buildTree([4, 2, 7, 1, 3]), 5))); // []

How it works

O(h) time and O(h) stack space. Each step ignores a whole side of the tree.

Approach 3A loop instead of recursion

The idea

Walk down with a pointer (a variable that points to the current node). Move left or right until you find the value or fall off the tree.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function searchBST(root, val) {  let cur = root;  while (cur !== null && cur.val !== val) {    cur = val < cur.val ? cur.left : cur.right;  }  return cur;}console.log(serialize(searchBST(buildTree([4, 2, 7, 1, 3]), 2))); // [2, 1, 3]console.log(serialize(searchBST(buildTree([4, 2, 7, 1, 3]), 5))); // []

How it works

O(h) time and O(1) extra space.

Which approach should you use?

Use the loop. It is short to write correctly and needs no stack. The brute force is a trap only because it ignores the BST property that the question gave you. (LeetCode 700.)

Q2Insert into a binary search treeMedium

Insert a value (one that is not already in the tree) into a BST and return the root. Any valid BST as a result is accepted.

Example 1

Input: root = [4, 2, 7, 1, 3], val = 5

Output: [4, 2, 7, 1, 3, 5]

Explanation: 5 > 4, so go right. 5 < 7, so go left. That spot is empty, so 5 becomes the left child of 7.

Example 2

Input: root = [], val = 5

Output: [5]

Explanation: Inserting into an empty tree makes the new node the root.

Stuck? Open one hint at a time

Hint 1

To insert, search for the empty place where the value should be.

Hint 2

You can always attach the new value as a leaf (a node with no children). No existing node has to move.

Show all 2 solutions with explanations

Approach 1Recursive

The idea

If the node is null, return a new node. Otherwise call the function on the correct side, and attach the result back to the node.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function insertIntoBST(root, val) {  if (root === null) return new TreeNode(val);  if (val < root.val) root.left = insertIntoBST(root.left, val);  else root.right = insertIntoBST(root.right, val);  return root;}console.log(serialize(insertIntoBST(buildTree([4, 2, 7, 1, 3]), 5)));  // [4, 2, 7, 1, 3, 5]console.log(serialize(insertIntoBST(buildTree([]), 5)));                // [5]console.log(serialize(insertIntoBST(buildTree([40, 20, 60, 10, 30, 50, 70]), 25))); // [40, 20, 60, 10, 30, 50, 70, null, null, 25]

How it works

O(h) time and space. Setting root.left = ... again on the way back does no harm when nothing changed. It does the real work when a new leaf appears.

Approach 2A loop

The idea

Walk down to the last node on the path. Attach the new node to its empty side.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function insertIntoBST(root, val) {  const fresh = new TreeNode(val);  if (root === null) return fresh;  let cur = root;  while (true) {    if (val < cur.val) {      if (cur.left === null) { cur.left = fresh; break; }      cur = cur.left;    } else {      if (cur.right === null) { cur.right = fresh; break; }      cur = cur.right;    }  }  return root;}console.log(serialize(insertIntoBST(buildTree([4, 2, 7, 1, 3]), 5)));  // [4, 2, 7, 1, 3, 5]console.log(serialize(insertIntoBST(buildTree([]), 5)));                // [5]

How it works

O(h) time, O(1) extra space. Handle the empty tree on its own, because there is no node to attach to.

Which approach should you use?

Either one is fine. The recursive one is shorter. Several results are valid (the judge accepts any valid BST), but adding a leaf is the simplest. (LeetCode 701.)

Q3Delete node in a BSTMedium

Delete the node with value key from a BST (if present) and return the root of the resulting BST.

Example 1

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

Output: [5, 4, 6, 2, null, null, 7]

Explanation: 3 has two children. Its successor (the next larger value) 4 takes its place.

Example 2

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

Output: [5, 3, 6, 2, 4, null, 7]

Explanation: 0 is not in the tree, so nothing changes.

Example 3

Input: root = [], key = 0

Output: []

Explanation: There is nothing to delete.

Stuck? Open one hint at a time

Hint 1

First search for the key. Then think about how many children the node has.

Hint 2

If it has zero or one child, replace the node with that child (or with null).

Hint 3

If it has two children, the smallest value on its right side is the next larger value. That value can take the place of this node.

Show all 3 solutions with explanations

Approach 1Brute force: rebuild the whole tree

The idea

Read all the values in inorder (sorted) order. Leave out the key. Build a balanced BST from the rest.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function deleteNode(root, key) {  const values = [];  (function inorder(n) { if (n) { inorder(n.left); if (n.val !== key) values.push(n.val); inorder(n.right); } })(root);  function build(lo, hi) {    if (lo > hi) return null;    const mid = Math.floor((lo + hi) / 2);    return new TreeNode(values[mid], build(lo, mid - 1), build(mid + 1, hi));  }  return build(0, values.length - 1);}const result = deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 3);const out = [];(function inorder(n) { if (n) { inorder(n.left); out.push(n.val); inorder(n.right); } })(result);console.log(out); // [2, 4, 5, 6, 7]

How it works

O(n) time and space. It rebuilds the whole tree even if you only remove one leaf. The result is a valid BST, but it is much more work than needed.

Approach 2Recursion with the inorder successor (the next larger value)

The idea

If the key is smaller, delete in the left side. If it is larger, delete in the right side.
If you find it and it has no left child, return the right child. If it has no right child, return the left child.
If it has two children, copy the smallest value of the right side into this node. Then delete that value from the right side.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function deleteNode(root, key) {  if (root === null) 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 === null) return root.right;    if (root.right === null) return root.left;    let succ = root.right;    while (succ.left !== null) succ = succ.left;    root.val = succ.val;    root.right = deleteNode(root.right, succ.val);  }  return root;}console.log(serialize(deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 3))); // [5, 4, 6, 2, null, null, 7]console.log(serialize(deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 0))); // [5, 3, 6, 2, 4, null, 7]console.log(serialize(deleteNode(buildTree([]), 0)));                        // []

How it works

O(h) time. The successor never has a left child, so deleting it is an easy case.

Approach 3Re-link nodes instead of copying values

The idea

For a node with two children, hang its left side under the successor (the leftmost node of the right side). Then return the right side in its place. No values are copied, so this is good when nodes are big objects.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function deleteNode(root, key) {  if (root === null) return null;  if (key < root.val) { root.left = deleteNode(root.left, key); return root; }  if (key > root.val) { root.right = deleteNode(root.right, key); return root; }  if (root.left === null) return root.right;  if (root.right === null) return root.left;  let succ = root.right;  while (succ.left !== null) succ = succ.left;  succ.left = root.left;          // everything on the left is smaller than the successor  return root.right;              // the right side takes the place of this node}console.log(serialize(deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 3))); // [5, 4, 6, 2, null, null, 7]console.log(serialize(deleteNode(buildTree([5, 3, 6, 2, 4, null, 7]), 5))); // [6, 3, 7, 2, 4]

How it works

Also O(h) time. It can make the tree a bit taller than the copy method, but it is still a valid BST.

Which approach should you use?

The recursive successor version is the standard answer. Know the three cases well. The re-linking version is a good follow-up. (LeetCode 450.)

Q4Validate binary search treeMedium

Return whether a binary tree is a valid BST: for every node, all values on the left side are smaller, all values on the right side are larger, and both sides are valid BSTs too.

Example 1

Input: root = [2, 1, 3]

Output: true

Explanation: 1 < 2 < 3.

Example 2

Input: root = [5, 1, 4, null, null, 3, 6]

Output: false

Explanation: 3 is on the right side of 5 but is smaller than 5. It looks fine next to its own parent 4, but it breaks the rule for 5.

Stuck? Open one hint at a time

Hint 1

Checking each node against its children is not enough. Which ancestors (the parent, grandparent, and so on) limit a deep node?

Hint 2

Carry a lower limit and an upper limit down the tree. Update one of them at each step.

Hint 3

Or think about what the inorder walk of a BST looks like.

Show all 3 solutions with explanations

Approach 1Brute force: compare with the whole left and right sides

The idea

For every node, find the largest value on its left side and the smallest value on its right side, and compare them with the node. Do this for all nodes.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isValidBST(root) {  function max(n) { return n === null ? -Infinity : Math.max(n.val, max(n.left), max(n.right)); }  function min(n) { return n === null ? Infinity : Math.min(n.val, min(n.left), min(n.right)); }  if (root === null) return true;  if (max(root.left) >= root.val || min(root.right) <= root.val) return false;  return isValidBST(root.left) && isValidBST(root.right);}console.log(isValidBST(buildTree([2, 1, 3])));                       // trueconsole.log(isValidBST(buildTree([5, 1, 4, null, null, 3, 6])));     // false

How it works

Correct, but each node scans everything below it. It takes O(n²) on a tree shaped like a chain.

Approach 2Pass down a lower and an upper limit

The idea

Start with the limits (−∞, +∞), which means no limit.
A node must be strictly between its limits.
Left child: new upper limit = this value. Right child: new lower limit = this value.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isValidBST(root) {  function check(node, lo, hi) {    if (node === null) 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, -Infinity, Infinity);}console.log(isValidBST(buildTree([2, 1, 3])));                       // trueconsole.log(isValidBST(buildTree([5, 1, 4, null, null, 3, 6])));     // falseconsole.log(isValidBST(buildTree([2147483647])));                    // true

How it works

O(n) time, O(h) space. We use Infinity, not the smallest or largest whole number. Then a node that really holds the smallest or largest integer does not fail by mistake.

Approach 3Inorder must be strictly increasing

The idea

Do an inorder walk (with your own stack, so we can stop early) and remember the previous value. If any value is not larger than the previous one, the tree is not a BST.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function isValidBST(root) {  const stack = [];  let cur = root;  let prev = -Infinity;  while (cur !== null || stack.length > 0) {    while (cur !== null) { stack.push(cur); cur = cur.left; }    cur = stack.pop();    if (cur.val <= prev) return false;    prev = cur.val;    cur = cur.right;  }  return true;}console.log(isValidBST(buildTree([2, 1, 3])));                       // trueconsole.log(isValidBST(buildTree([5, 1, 4, null, null, 3, 6])));     // false

How it works

O(n) time, O(h) space. It stops at the first value that breaks the rule. It works because a tree is a BST exactly when its inorder list is strictly increasing.

Which approach should you use?

Use limits or inorder. Both are O(n). The limits version also works for other problems where every ancestor limits a node. Never give the answer that checks only the parent. (LeetCode 98.)

Q5Kth smallest element in a BSTMedium

Return the k-th smallest value in a BST (counting from 1). It is guaranteed that 1 ≤ k ≤ the number of nodes.

Example 1

Input: root = [3, 1, 4, null, 2], k = 1

Output: 1

Explanation: In inorder the values come as 1, 2, 3, 4. The first one is 1.

Example 2

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

Output: 3

Explanation: In inorder the values come as 1, 2, 3, 4, 5, 6. The third one is 3.

Stuck? Open one hint at a time

Hint 1

Which walk lists a BST in sorted order?

Hint 2

Do you need to finish the walk once you have counted k nodes?

Show all 3 solutions with explanations

Approach 1Collect the full inorder list

The idea

Walk the whole tree in inorder and store every value. Then take the item at index k − 1.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function kthSmallest(root, k) {  const values = [];  (function inorder(n) {    if (n === null) return;    inorder(n.left);    values.push(n.val);    inorder(n.right);  })(root);  return values[k - 1];}console.log(kthSmallest(buildTree([3, 1, 4, null, 2]), 1));                  // 1console.log(kthSmallest(buildTree([5, 3, 6, 2, 4, null, null, 1]), 3));      // 3

How it works

O(n) time and space, even when k is tiny.

Approach 2Recursive inorder with a counter

The idea

Count the nodes as you visit them. Remember the value when the count reaches k. Skip the right side once you have the answer.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function kthSmallest(root, k) {  let count = 0;  let answer = null;  function inorder(n) {    if (n === null || answer !== null) return;    inorder(n.left);    count++;    if (count === k) { answer = n.val; return; }    inorder(n.right);  }  inorder(root);  return answer;}console.log(kthSmallest(buildTree([3, 1, 4, null, 2]), 1));                  // 1console.log(kthSmallest(buildTree([5, 3, 6, 2, 4, null, null, 1]), 3));      // 3

How it works

O(h + k) time and O(h) space. Once the answer is set, every remaining call returns at once. A value of 0 works correctly, because we test answer !== null, not whether the value is "truthy" (JavaScript treats 0 as false in an if).

Approach 3Inorder with your own stack and an early exit

The idea

Push the whole chain of left children onto a stack. Pop to get the next smallest value and decrease k. Return when k reaches 0. Otherwise move to the right child.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function kthSmallest(root, k) {  const stack = [];  let cur = root;  while (cur !== null || stack.length > 0) {    while (cur !== null) { stack.push(cur); cur = cur.left; }    cur = stack.pop();    if (--k === 0) return cur.val;    cur = cur.right;  }  return undefined;}console.log(kthSmallest(buildTree([3, 1, 4, null, 2]), 1));                  // 1console.log(kthSmallest(buildTree([5, 3, 6, 2, 4, null, null, 1]), 3));      // 3console.log(kthSmallest(buildTree([5, 3, 6, 2, 4, null, null, 1]), 6));      // 6

How it works

O(h + k) time, O(h) space. Suppose the tree changes often and you must answer many queries. Then store in each node the size of the part below it. You can then choose left or right by using these counts, in O(h) per query.

Which approach should you use?

Use the version with your own stack. It uses the BST property, stops early and has no limit on recursion depth. (LeetCode 230.)

Q6Convert sorted array to binary search treeEasy

You get an array sorted from small to large. Convert it to a height-balanced BST: at every node, the heights of the left side and right side differ by at most 1. Any valid answer is accepted.

Example 1

Input: nums = [-10, -3, 0, 5, 9]

Output: [0, -3, 9, -10, null, 5]

Explanation: 0 is the middle. -10 and -3 go left, and 5 and 9 go right. [0, -10, 5, null, -3, null, 9] is also accepted.

Example 2

Input: nums = [1, 3]

Output: [3, 1]

Explanation: Either value can be the root. [1, null, 3] is also accepted.

Stuck? Open one hint at a time

Hint 1

Which element should be the root, so that both sides get about the same number of nodes?

Hint 2

After you choose the root, the left part and the right part of the array are the same problem again.

Show all 3 solutions with explanations

Approach 1Brute force: insert one by one

The idea

Insert the numbers in the order of the array, using the normal BST insert.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function insert(root, val) {  if (root === null) return new TreeNode(val);  if (val < root.val) root.left = insert(root.left, val);  else root.right = insert(root.right, val);  return root;}function height(n) { return n === null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }function sortedArrayToBST(nums) {  let root = null;  for (const x of nums) root = insert(root, x);  return root;}console.log(height(sortedArrayToBST([-10, -3, 0, 5, 9]))); // 5   (a chain, not balanced)

How it works

It is a valid BST but it is not height-balanced. Sorted input makes a chain, and the whole build costs O(n²).

Approach 2Middle element as root, slicing the array

The idea

Take the middle element as the root. Build the left child from the left slice (the left part of the array) and the right child from the right slice.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function sortedArrayToBST(nums) {  if (nums.length === 0) return null;  const mid = Math.ceil((nums.length - 1) / 2);  return new TreeNode(    nums[mid],    sortedArrayToBST(nums.slice(0, mid)),    sortedArrayToBST(nums.slice(mid + 1)),  );}console.log(serialize(sortedArrayToBST([-10, -3, 0, 5, 9]))); // [0, -3, 9, -10, null, 5]console.log(serialize(sortedArrayToBST([1, 3])));              // [3, 1]

How it works

The tree is balanced, but each slice copies elements. The total time is O(n log n).

Approach 3Middle element as root, with index bounds

The idea

Do not copy. Pass the positions lo and hi instead. The root is nums[mid]. Build the left child from lo..mid-1 and the right child from mid+1..hi.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}// Tree -> level-order array with null gaps (trailing nulls trimmed)function serialize(root) {  const out = [], queue = [root];  for (let head = 0; head < queue.length; head++) {    const node = queue[head];    if (node === null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out[out.length - 1] === null) out.pop();  return out;}function sortedArrayToBST(nums) {  function build(lo, hi) {    if (lo > hi) return null;    const mid = Math.ceil((lo + hi) / 2);    return new TreeNode(nums[mid], build(lo, mid - 1), build(mid + 1, hi));  }  return build(0, nums.length - 1);}console.log(serialize(sortedArrayToBST([-10, -3, 0, 5, 9]))); // [0, -3, 9, -10, null, 5]console.log(serialize(sortedArrayToBST([1, 3])));              // [3, 1]console.log(serialize(sortedArrayToBST([])));                  // []

How it works

O(n) time (each element becomes exactly one node) and O(log n) recursion depth. The tree is height-balanced because the two halves differ in size by at most one.

Which approach should you use?

Use the version with positions. Show that inserting in sorted order gives a chain, then fix it with "middle first". (LeetCode 108.)

Q7Two sum IV: input is a BSTEasy

You get a BST and an integer k. Return true if two different nodes have values that add up to k.

Example 1

Input: root = [5, 3, 6, 2, 4, null, 7], k = 9

Output: true

Explanation: 2 + 7 = 9.

Example 2

Input: root = [5, 3, 6, 2, 4, null, 7], k = 28

Output: false

Explanation: No two values add up to 28.

Stuck? Open one hint at a time

Hint 1

You solved "two sum" with a hash set before. You can walk a tree and fill a set at the same time.

Hint 2

The inorder walk of a BST gives a sorted list. Which technique works on a sorted array?

Hint 3

Could two pointers walk the BST directly? One would start at the smallest value and go up. The other would start at the largest value and go down.

Show all 3 solutions with explanations

Approach 1Hash set while walking the tree

The idea

A hash set is a collection that remembers values and tells you in about one step whether it has seen a value before. Visit every node. If you saw k − node.val earlier, return true. Otherwise remember the value.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function findTarget(root, k) {  const seen = new Set();  function dfs(node) {    if (node === null) return false;    if (seen.has(k - node.val)) return true;    seen.add(node.val);    return dfs(node.left) || dfs(node.right);  }  return dfs(root);}console.log(findTarget(buildTree([5, 3, 6, 2, 4, null, 7]), 9));    // trueconsole.log(findTarget(buildTree([5, 3, 6, 2, 4, null, 7]), 28));   // false

How it works

O(n) time and O(n) space. It works for any binary tree, but it does not use the BST property.

Approach 2Inorder array plus two pointers

The idea

Turn the BST into a sorted array with inorder. Then run the classic two-pointer search from both ends.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function findTarget(root, k) {  const values = [];  (function inorder(n) {    if (n === null) return;    inorder(n.left);    values.push(n.val);    inorder(n.right);  })(root);  let i = 0, j = values.length - 1;  while (i < j) {    const sum = values[i] + values[j];    if (sum === k) return true;    if (sum < k) i++;    else j--;  }  return false;}console.log(findTarget(buildTree([5, 3, 6, 2, 4, null, 7]), 9));    // trueconsole.log(findTarget(buildTree([5, 3, 6, 2, 4, null, 7]), 28));   // false

How it works

O(n) time and O(n) space. The second step is very simple.

Approach 3Two iterators with stacks (O(h) space)

The idea

Keep two stacks. One gives values from small to large (it holds the chain of left children, like the inorder with a stack). The other gives values from large to small (it holds the chain of right children). If the sum is too small, move the small pointer up. If the sum is too big, move the large pointer down.

JavaScript

class TreeNode { constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }function buildTree(arr) {                           // level-order array, null marks a missing child  if (arr.length === 0 || arr[0] === null) return null;  const root = new TreeNode(arr[0]);  const queue = [root];  let i = 1;  while (queue.length && i < arr.length) {    const node = queue.shift();    if (arr[i] !== null) { node.left = new TreeNode(arr[i]); queue.push(node.left); }    i++;    if (i < arr.length && arr[i] !== null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function findTarget(root, k) {  if (root === null) return false;  const asc = [], desc = [];  const pushLeft = (n) => { while (n !== null) { asc.push(n); n = n.left; } };  const pushRight = (n) => { while (n !== null) { desc.push(n); n = n.right; } };  const nextSmall = () => { const n = asc.pop(); pushLeft(n.right); return n.val; };  const nextLarge = () => { const n = desc.pop(); pushRight(n.left); return n.val; };  pushLeft(root);  pushRight(root);  let lo = nextSmall(), hi = nextLarge();  while (lo < hi) {    const sum = lo + hi;    if (sum === k) return true;    if (sum < k) lo = nextSmall();    else hi = nextLarge();  }  return false;}console.log(findTarget(buildTree([5, 3, 6, 2, 4, null, 7]), 9));    // trueconsole.log(findTarget(buildTree([5, 3, 6, 2, 4, null, 7]), 28));   // false

How it works

O(n) time and only O(h) space, because each stack holds at most one path from the root to a node. It is the most impressive answer, but the easiest to get wrong. The set version is a perfectly good interview answer.

Which approach should you use?

Start with the hash set. It works on any tree. Then mention that a BST allows two pointers on the inorder array, or O(h) space with two stacks. (LeetCode 653.)

Make it stick

Make it stick — close this page, then

Say the BST property, and explain why "every" (not just the children) matters.
Describe the three cases of deletion, and what replaces a node that has two children.
Explain why checking only the parent of a node fails to validate a BST, and how limits fix it.
Explain how inorder gives the k-th smallest value, and how the stack lets you stop early.
Explain why inserting in sorted order makes a BST degenerate, and how choosing the middle prevents that.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

Lesson 45 finishes the tree part with two classic groups of problems. The first is the lowest common ancestor: the lowest node that has two given nodes below it. In a BST it is quick to find, using today's property. The second is rebuilding a tree from its walks. There, the inorder list splits the other lists into a left part and a right part.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated 7 Oct 2026 · How these lessons are made

Keep learning

Related series

On this page

The BST property

Search

Insert

Delete: three cases

Validate a BST

K-th smallest with inorder

Traced: the 3rd smallest value

Build a balanced BST from a sorted array

Why an unbalanced BST is O(n)

Practice questions

Make it stick

What's next

Practise on LeetCode

Keep learning