GUIDE · Trees

Trees & BST patterns

Hierarchical nodes; a BINARY tree has <= 2 children; a BST keeps left < node < right so INORDER traversal is sorted.

lesson18 sectionsruns in browser77 asserts469 lines

At a glance

WHAT: Hierarchical nodes; a BINARY tree has <= 2 children; a BST keeps left < node < right so INORDER traversal is sorted.
TELL: "root", "leaf", "ancestor", "subtree", "level", "depth", "sorted order" with inserts/deletes, "kth smallest", "range query".
SAY: root / leaf / internal node / parent / child / sibling / subtree. DEPTH = edges from root down to node. HEIGHT = edges from node down to deepest leaf. LEVEL = depth + 1 (or depth, say which). FULL (0 or 2 children), COMPLETE (filled left-to-right), PERFECT (all leaves same depth), BALANCED (|h(L)-h(R)| <= 1 everywhere), DEGENERATE (a linked list; BST worst case). DFS = preorder (N L R) / inorder (L N R) / postorder (L R N). BFS = level order. LCA = lowest common ancestor. DIAMETER = longest path between any two nodes. HORIZONTAL DISTANCE for top/bottom view. Inorder SUCCESSOR = next larger; PREDECESSOR = next smaller.
BIG-O: traversal O(n) time, O(h) stack (h = height; log n balanced, n worst). BST search/insert/delete O(h). Self-balancing (AVL / red-black) keeps h = O(log n) — name them, you won't be asked to implement them.

The idea#

Picture a family tree drawn on a big sheet of paper. One person at the top, the root. Each person can have people hanging under them. You can point at anyone and talk about their parent, their children, their siblings, and the little tree that hangs from them, the subtree.

A binary tree gives each node at most two children, left and right. A binary search tree keeps every value in the left subtree smaller than the node, and every value in the right subtree larger, so an inorder walk comes out sorted. Walking every node is O(n) time and O(h) stack, where h is the height. Search, insert, and delete on a binary search tree are O(h): O(log n) when the tree stays balanced, and O(n) when it degenerates into a linked list. AVL and red-black trees are the names that keep h at O(log n). Name them. Building one is a different assignment.

Depth counts edges from the root down to a node. Height counts edges from a node down to its deepest leaf. A level is depth plus one. Full means 0 or 2 children. Complete fills left to right. Perfect puts every leaf at the same depth. Balanced means the two subtree heights differ by at most 1 everywhere.

Preorder visits node, left, right. Inorder visits left, node, right. Postorder visits left, right, node. Breadth-first search visits a level at a time. The lowest common ancestor is the deepest node that still covers both targets. Diameter is the longest path, in edges. Horizontal distance is how far left or right of the root a node sits.

Why it matters#

Trees show up whenever one thing contains other things: a folder, a comment thread, a decision. The binary search tree finds, inserts, and deletes in O(h) and hands you sorted order for free, because inorder is sorted.

Checking a node only against its own children accepts a tree that breaks further down. Carry a low bound and a high bound into every call. The left child inherits the parent's value as its new high. The right child inherits it as its new low.

The call stack of a recursive walk is O(h). A skinny tree has h = n. Section 2 on the sheet puts the same three orders on an explicit stack.

A small example#

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);} const tree = {  val: 5,  left: { val: 1, left: null, right: null },  right: { val: 4, left: { val: 3, left: null, right: null }, right: { val: 6, left: null, right: null } },};const ok = isValidBST(tree);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);
}

const tree = {
  val: 5,
  left: { val: 1, left: null, right: null },
  right: { val: 4, left: { val: 3, left: null, right: null }, right: { val: 6, left: null, right: null } },
};
const ok = isValidBST(tree);

ok is false. The node 3 sits under 5's right side, and 3 is smaller than 5. Comparing 4 only with its own children would have waved that through.

What the code below is doing#

Section 0 turns a level-order array into a tree and back. Nulls are holes. Section 1 is recursive preorder, inorder, and postorder, O(n) time and O(h) stack. Section 2 is the same three walks on an explicit stack: preorder pushes right first, inorder exhausts left then steps right, postorder is a reversed modified preorder. Section 3 is level order, O(n) time and O(w) at the widest level, plus zigzag.

Section 4 is the views. Right side is the last node of each level, left side the first. Vertical buckets group by horizontal distance in breadth-first order. Top view keeps the first value in a column, bottom view the last, vertical order the whole column. Boundary goes anticlockwise: root, left edge without leaves, leaves left to right, right edge upward without leaves.

Section 5 measures, all O(n): max depth, min depth (a one-child node is not a leaf), count, sum, diameter as best left-height plus right-height in edges, and balanced via a -1 sentinel. Section 6 is invert, same tree, symmetric as one side against the mirror of the other, and subtree, O(n · m) by checking sameness at every node. Section 7 is root-to-leaf sum, all paths by push and pop, and max path sum, keeping the bend through the node and returning only the better arm.

Section 8 is the general lowest common ancestor. A node counts as an ancestor of itself. From section 9 the sheet is a search tree and duplicates are ignored, so say which side they would take if a spec allows them. Section 9 is search, insert, min, and max, each O(h), and inorder comes out sorted. Section 10 deletes a leaf or one child by returning the surviving child, and two children by swapping in the inorder successor. Section 11 is the bounds check. A strictly increasing inorder is the other correct test.

Section 12 spends the sorted inorder. Kth smallest stops at k. The successor is the last node where the walk stepped left. Closest keeps the best distance on the search path. Range sum prunes a subtree that sits outside the window. Two-sum walks the inorder array from both ends. The search-tree ancestor walks down while both targets share a side. Section 13 builds a balanced tree by taking the middle of a sorted array, O(n). Section 14 rebuilds from preorder plus inorder, and the left subtree is built first. Postorder plus inorder takes the root from the end and builds the right side first. Section 15 serializes preorder with # for null. Section 16 flattens by visiting right, then left, then stitching. Section 17 loops over children for an n-ary node.

When you talk about it, say this: inorder of a binary search tree is sorted, search and update cost O(h), and a balanced tree keeps h at O(log n).

Everything below is the demonstration. Same idea, written as code you can run.

JSalgorithms/trees-bst.js · setup

'use strict';const assert = require('node:assert/strict');'use strict';
const assert = require('node:assert/strict');

Output

Node + helpers (LeetCode level-order array <-> tree; nulls are holes)#

class TreeNode {  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }}function fromLevelOrder(arr) {  if (!arr.length || 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++;    if (i < arr.length && arr[i] != null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }    i++;  }  return root;}function toLevelOrder(root) {  const out = [];  const queue = [root];  while (queue.length) {    const node = queue.shift();    if (node == null) { out.push(null); continue; }    out.push(node.val);    queue.push(node.left, node.right);  }  while (out.length && out.at(-1) == null) out.pop();  return out;} //            1//          /   \//         2     3//        / \     \//       4   5     6//          ///         7const T = fromLevelOrder([1, 2, 3, 4, 5, null, 6, null, null, 7]);class TreeNode {
  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right; }
}
function fromLevelOrder(arr) {
  if (!arr.length || 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++;
    if (i < arr.length && arr[i] != null) { node.right = new TreeNode(arr[i]); queue.push(node.right); }
    i++;
  }
  return root;
}
function toLevelOrder(root) {
  const out = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    if (node == null) { out.push(null); continue; }
    out.push(node.val);
    queue.push(node.left, node.right);
  }
  while (out.length && out.at(-1) == null) out.pop();
  return out;
}

//            1
//          /   \
//         2     3
//        / \     \
//       4   5     6
//          /
//         7
const T = fromLevelOrder([1, 2, 3, 4, 5, null, 6, null, null, 7]);

Verified by 1 assert

assert.deepEqual(toLevelOrder(T), [1, 2, 3, 4, 5, null, 6, null, null, 7]);assert.deepEqual(toLevelOrder(T), [1, 2, 3, 4, 5, null, 6, null, null, 7]);

DFS recursive#

preorder / inorder / postorder

O(n) / O(h)

const preorder = (n, out = []) => (n && (out.push(n.val), preorder(n.left, out), preorder(n.right, out)), out);const inorder = (n, out = []) => (n && (inorder(n.left, out), out.push(n.val), inorder(n.right, out)), out);const postorder = (n, out = []) => (n && (postorder(n.left, out), postorder(n.right, out), out.push(n.val)), out);const preorder = (n, out = []) => (n && (out.push(n.val), preorder(n.left, out), preorder(n.right, out)), out);
const inorder = (n, out = []) => (n && (inorder(n.left, out), out.push(n.val), inorder(n.right, out)), out);
const postorder = (n, out = []) => (n && (postorder(n.left, out), postorder(n.right, out), out.push(n.val)), out);

Verified by 3 asserts

assert.deepEqual(preorder(T), [1, 2, 4, 5, 7, 3, 6]);assert.deepEqual(inorder(T), [4, 2, 7, 5, 1, 3, 6]);assert.deepEqual(postorder(T), [4, 7, 5, 2, 6, 3, 1]);assert.deepEqual(preorder(T), [1, 2, 4, 5, 7, 3, 6]);
assert.deepEqual(inorder(T), [4, 2, 7, 5, 1, 3, 6]);
assert.deepEqual(postorder(T), [4, 7, 5, 2, 6, 3, 1]);

DFS iterative#

explicit stack (ask: "recursion depth could overflow?")

function preorderIter(root) {                      // push right first so left pops first  const out = [], stack = root ? [root] : [];  while (stack.length) {    const n = stack.pop();    out.push(n.val);    if (n.right) stack.push(n.right);    if (n.left) stack.push(n.left);  }  return out;}function inorderIter(root) {                       // go left as far as possible, pop, go right  const out = [], stack = [];  let cur = root;  while (cur || stack.length) {    while (cur) { stack.push(cur); cur = cur.left; }    cur = stack.pop();    out.push(cur.val);    cur = cur.right;  }  return out;}function postorderIter(root) {                     // "reverse of modified preorder" (N R L reversed)  const out = [], stack = root ? [root] : [];  while (stack.length) {    const n = stack.pop();    out.push(n.val);    if (n.left) stack.push(n.left);    if (n.right) stack.push(n.right);  }  return out.reverse();}function preorderIter(root) {                      // push right first so left pops first
  const out = [], stack = root ? [root] : [];
  while (stack.length) {
    const n = stack.pop();
    out.push(n.val);
    if (n.right) stack.push(n.right);
    if (n.left) stack.push(n.left);
  }
  return out;
}
function inorderIter(root) {                       // go left as far as possible, pop, go right
  const out = [], stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    out.push(cur.val);
    cur = cur.right;
  }
  return out;
}
function postorderIter(root) {                     // "reverse of modified preorder" (N R L reversed)
  const out = [], stack = root ? [root] : [];
  while (stack.length) {
    const n = stack.pop();
    out.push(n.val);
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);
  }
  return out.reverse();
}

Verified by 4 asserts

assert.deepEqual(preorderIter(T), preorder(T));assert.deepEqual(inorderIter(T), inorder(T));assert.deepEqual(postorderIter(T), postorder(T));assert.deepEqual(inorderIter(null), []);assert.deepEqual(preorderIter(T), preorder(T));
assert.deepEqual(inorderIter(T), inorder(T));
assert.deepEqual(postorderIter(T), postorder(T));
assert.deepEqual(inorderIter(null), []);

BFS#

level order

O(n) / O(w) (w = max width)

function levelOrder(root) {  const out = [];  let level = root ? [root] : [];  while (level.length) {    out.push(level.map(n => n.val));    level = level.flatMap(n => [n.left, n.right].filter(Boolean));  }  return out;}function zigzag(root) {  return levelOrder(root).map((lvl, i) => (i % 2 ? lvl.reverse() : lvl));}function levelOrder(root) {
  const out = [];
  let level = root ? [root] : [];
  while (level.length) {
    out.push(level.map(n => n.val));
    level = level.flatMap(n => [n.left, n.right].filter(Boolean));
  }
  return out;
}
function zigzag(root) {
  return levelOrder(root).map((lvl, i) => (i % 2 ? lvl.reverse() : lvl));
}

Verified by 3 asserts

assert.deepEqual(levelOrder(T), [[1], [2, 3], [4, 5, 6], [7]]);assert.deepEqual(zigzag(T), [[1], [3, 2], [4, 5, 6], [7]]);assert.deepEqual(levelOrder(null), []);assert.deepEqual(levelOrder(T), [[1], [2, 3], [4, 5, 6], [7]]);
assert.deepEqual(zigzag(T), [[1], [3, 2], [4, 5, 6], [7]]);
assert.deepEqual(levelOrder(null), []);

VIEWS#

"what do you see if you flip the tree on its side?"

// RIGHT SIDE VIEW = last node of every BFS level. LEFT SIDE VIEW = first node.const rightSideView = root => levelOrder(root).map(lvl => lvl.at(-1));const leftSideView = root => levelOrder(root).map(lvl => lvl[0]); // TOP VIEW / BOTTOM VIEW = BFS with HORIZONTAL DISTANCE (left = hd-1, right = hd+1).// Top view keeps the FIRST node seen per hd; bottom view keeps the LAST.function verticalBuckets(root) {                    // Map<hd, vals in BFS order>, keys sorted  const byHd = new Map();  const queue = root ? [[root, 0]] : [];  while (queue.length) {    const [n, hd] = queue.shift();    if (!byHd.has(hd)) byHd.set(hd, []);    byHd.get(hd).push(n.val);    if (n.left) queue.push([n.left, hd - 1]);    if (n.right) queue.push([n.right, hd + 1]);  }  return [...byHd.keys()].sort((a, b) => a - b).map(k => byHd.get(k));}const topView = root => verticalBuckets(root).map(col => col[0]);const bottomView = root => verticalBuckets(root).map(col => col.at(-1));const verticalOrder = root => verticalBuckets(root);        // LeetCode "vertical order traversal" (simple version) // BOUNDARY TRAVERSAL (anticlockwise): root, left edge top-down (no leaves),// all leaves left-to-right, right edge bottom-up (no leaves).function boundary(root) {  if (!root) return [];  const isLeaf = n => !n.left && !n.right;  const out = [root.val];  if (isLeaf(root)) return out;  for (let n = root.left; n && !isLeaf(n); n = n.left ?? n.right) out.push(n.val);  (function leaves(n) { if (!n) return; if (isLeaf(n)) out.push(n.val); leaves(n.left); leaves(n.right); })(root);  const right = [];  for (let n = root.right; n && !isLeaf(n); n = n.right ?? n.left) right.push(n.val);  return out.concat(right.reverse());}// RIGHT SIDE VIEW = last node of every BFS level. LEFT SIDE VIEW = first node.
const rightSideView = root => levelOrder(root).map(lvl => lvl.at(-1));
const leftSideView = root => levelOrder(root).map(lvl => lvl[0]);

// TOP VIEW / BOTTOM VIEW = BFS with HORIZONTAL DISTANCE (left = hd-1, right = hd+1).
// Top view keeps the FIRST node seen per hd; bottom view keeps the LAST.
function verticalBuckets(root) {                    // Map<hd, vals in BFS order>, keys sorted
  const byHd = new Map();
  const queue = root ? [[root, 0]] : [];
  while (queue.length) {
    const [n, hd] = queue.shift();
    if (!byHd.has(hd)) byHd.set(hd, []);
    byHd.get(hd).push(n.val);
    if (n.left) queue.push([n.left, hd - 1]);
    if (n.right) queue.push([n.right, hd + 1]);
  }
  return [...byHd.keys()].sort((a, b) => a - b).map(k => byHd.get(k));
}
const topView = root => verticalBuckets(root).map(col => col[0]);
const bottomView = root => verticalBuckets(root).map(col => col.at(-1));
const verticalOrder = root => verticalBuckets(root);        // LeetCode "vertical order traversal" (simple version)

// BOUNDARY TRAVERSAL (anticlockwise): root, left edge top-down (no leaves),
// all leaves left-to-right, right edge bottom-up (no leaves).
function boundary(root) {
  if (!root) return [];
  const isLeaf = n => !n.left && !n.right;
  const out = [root.val];
  if (isLeaf(root)) return out;
  for (let n = root.left; n && !isLeaf(n); n = n.left ?? n.right) out.push(n.val);
  (function leaves(n) { if (!n) return; if (isLeaf(n)) out.push(n.val); leaves(n.left); leaves(n.right); })(root);
  const right = [];
  for (let n = root.right; n && !isLeaf(n); n = n.right ?? n.left) right.push(n.val);
  return out.concat(right.reverse());
}

Verified by 7 asserts

assert.deepEqual(rightSideView(T), [1, 3, 6, 7]);assert.deepEqual(leftSideView(T), [1, 2, 4, 7]);assert.deepEqual(topView(T), [4, 2, 1, 3, 6]);assert.deepEqual(bottomView(T), [4, 7, 5, 3, 6]);assert.deepEqual(verticalOrder(T), [[4], [2, 7], [1, 5], [3], [6]]);assert.deepEqual(boundary(T), [1, 2, 4, 7, 6, 3]);assert.deepEqual(boundary(fromLevelOrder([1])), [1]);assert.deepEqual(rightSideView(T), [1, 3, 6, 7]);
assert.deepEqual(leftSideView(T), [1, 2, 4, 7]);
assert.deepEqual(topView(T), [4, 2, 1, 3, 6]);
assert.deepEqual(bottomView(T), [4, 7, 5, 3, 6]);
assert.deepEqual(verticalOrder(T), [[4], [2, 7], [1, 5], [3], [6]]);
assert.deepEqual(boundary(T), [1, 2, 4, 7, 6, 3]);
assert.deepEqual(boundary(fromLevelOrder([1])), [1]);

Depth / height / size family#

all O(n)

const maxDepth = n => (n ? 1 + Math.max(maxDepth(n.left), maxDepth(n.right)) : 0);   // in NODESfunction minDepth(n) {                               // shortest root-to-LEAF; a one-child node is NOT a leaf  if (!n) return 0;  if (!n.left) return 1 + minDepth(n.right);  if (!n.right) return 1 + minDepth(n.left);  return 1 + Math.min(minDepth(n.left), minDepth(n.right));}const countNodes = n => (n ? 1 + countNodes(n.left) + countNodes(n.right) : 0);const sumNodes = n => (n ? n.val + sumNodes(n.left) + sumNodes(n.right) : 0);function diameter(root) {                            // longest path in EDGES; update best at every node  let best = 0;  (function height(n) {    if (!n) return 0;    const l = height(n.left), r = height(n.right);    best = Math.max(best, l + r);    return 1 + Math.max(l, r);  })(root);  return best;}function isBalanced(root) {                          // -1 sentinel bubbles "unbalanced" up in one pass  const h = n => {    if (!n) return 0;    const l = h(n.left); if (l === -1) return -1;    const r = h(n.right); if (r === -1) return -1;    return Math.abs(l - r) > 1 ? -1 : 1 + Math.max(l, r);  };  return h(root) !== -1;}const maxDepth = n => (n ? 1 + Math.max(maxDepth(n.left), maxDepth(n.right)) : 0);   // in NODES
function minDepth(n) {                               // shortest root-to-LEAF; a one-child node is NOT a leaf
  if (!n) return 0;
  if (!n.left) return 1 + minDepth(n.right);
  if (!n.right) return 1 + minDepth(n.left);
  return 1 + Math.min(minDepth(n.left), minDepth(n.right));
}
const countNodes = n => (n ? 1 + countNodes(n.left) + countNodes(n.right) : 0);
const sumNodes = n => (n ? n.val + sumNodes(n.left) + sumNodes(n.right) : 0);
function diameter(root) {                            // longest path in EDGES; update best at every node
  let best = 0;
  (function height(n) {
    if (!n) return 0;
    const l = height(n.left), r = height(n.right);
    best = Math.max(best, l + r);
    return 1 + Math.max(l, r);
  })(root);
  return best;
}
function isBalanced(root) {                          // -1 sentinel bubbles "unbalanced" up in one pass
  const h = n => {
    if (!n) return 0;
    const l = h(n.left); if (l === -1) return -1;
    const r = h(n.right); if (r === -1) return -1;
    return Math.abs(l - r) > 1 ? -1 : 1 + Math.max(l, r);
  };
  return h(root) !== -1;
}

Verified by 8 asserts

assert.equal(maxDepth(T), 4);assert.equal(minDepth(T), 3);assert.equal(minDepth(fromLevelOrder([1, 2])), 2);  // NOT 1 — root isn't a leafassert.equal(countNodes(T), 7);assert.equal(sumNodes(T), 28);assert.equal(diameter(T), 5);                        // 7-5-2-1-3-6assert.equal(isBalanced(T), true);assert.equal(isBalanced(fromLevelOrder([1, 2, null, 3])), false);assert.equal(maxDepth(T), 4);
assert.equal(minDepth(T), 3);
assert.equal(minDepth(fromLevelOrder([1, 2])), 2);  // NOT 1 — root isn't a leaf
assert.equal(countNodes(T), 7);
assert.equal(sumNodes(T), 28);
assert.equal(diameter(T), 5);                        // 7-5-2-1-3-6
assert.equal(isBalanced(T), true);
assert.equal(isBalanced(fromLevelOrder([1, 2, null, 3])), false);

Shape questions#

invert / same / symmetric / subtree

function invert(n) { if (n) { [n.left, n.right] = [invert(n.right), invert(n.left)]; } return n; }const isSame = (a, b) => (!a && !b) || (!!a && !!b && a.val === b.val && isSame(a.left, b.left) && isSame(a.right, b.right));const isSymmetric = root => !root || isSame(root.left, invert(structuredCloneTree(root.right)));function structuredCloneTree(n) { return n ? new TreeNode(n.val, structuredCloneTree(n.left), structuredCloneTree(n.right)) : null; }function isSubtree(root, sub) {                     // O(n*m); mention serialize+KMP or hashing for O(n+m)  if (!root) return !sub;  return isSame(root, sub) || isSubtree(root.left, sub) || isSubtree(root.right, sub);}const Tinv = invert(structuredCloneTree(T));function invert(n) { if (n) { [n.left, n.right] = [invert(n.right), invert(n.left)]; } return n; }
const isSame = (a, b) => (!a && !b) || (!!a && !!b && a.val === b.val && isSame(a.left, b.left) && isSame(a.right, b.right));
const isSymmetric = root => !root || isSame(root.left, invert(structuredCloneTree(root.right)));
function structuredCloneTree(n) { return n ? new TreeNode(n.val, structuredCloneTree(n.left), structuredCloneTree(n.right)) : null; }
function isSubtree(root, sub) {                     // O(n*m); mention serialize+KMP or hashing for O(n+m)
  if (!root) return !sub;
  return isSame(root, sub) || isSubtree(root.left, sub) || isSubtree(root.right, sub);
}
const Tinv = invert(structuredCloneTree(T));

Verified by 7 asserts

assert.deepEqual(toLevelOrder(Tinv), [1, 3, 2, 6, null, 5, 4, null, null, null, 7]);assert.deepEqual(inorder(Tinv), inorder(T).reverse());assert.equal(isSame(T, fromLevelOrder([1, 2, 3, 4, 5, null, 6, null, null, 7])), true);assert.equal(isSymmetric(fromLevelOrder([1, 2, 2, 3, 4, 4, 3])), true);assert.equal(isSymmetric(fromLevelOrder([1, 2, 2, null, 3, null, 3])), false);assert.equal(isSubtree(T, fromLevelOrder([5, 7])), true);assert.equal(isSubtree(T, fromLevelOrder([5])), false);assert.deepEqual(toLevelOrder(Tinv), [1, 3, 2, 6, null, 5, 4, null, null, null, 7]);
assert.deepEqual(inorder(Tinv), inorder(T).reverse());
assert.equal(isSame(T, fromLevelOrder([1, 2, 3, 4, 5, null, 6, null, null, 7])), true);
assert.equal(isSymmetric(fromLevelOrder([1, 2, 2, 3, 4, 4, 3])), true);
assert.equal(isSymmetric(fromLevelOrder([1, 2, 2, null, 3, null, 3])), false);
assert.equal(isSubtree(T, fromLevelOrder([5, 7])), true);
assert.equal(isSubtree(T, fromLevelOrder([5])), false);

Path questions#

root-to-leaf sums, all paths, max path sum (any-to-any)

function hasPathSum(n, target) {  if (!n) return false;  if (!n.left && !n.right) return n.val === target;  return hasPathSum(n.left, target - n.val) || hasPathSum(n.right, target - n.val);}function allPaths(root) {                            // backtracking down the tree  const out = [], path = [];  (function dfs(n) {    if (!n) return;    path.push(n.val);    if (!n.left && !n.right) out.push(path.join('->'));    dfs(n.left); dfs(n.right);    path.pop();  })(root);  return out;}function maxPathSum(root) {                          // at each node: best "arm" from each side (negative -> 0)  let best = -Infinity;  (function gain(n) {    if (!n) return 0;    const l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));    best = Math.max(best, n.val + l + r);          // path that BENDS at n    return n.val + Math.max(l, r);                 // path that CONTINUES up through n  })(root);  return best;}function hasPathSum(n, target) {
  if (!n) return false;
  if (!n.left && !n.right) return n.val === target;
  return hasPathSum(n.left, target - n.val) || hasPathSum(n.right, target - n.val);
}
function allPaths(root) {                            // backtracking down the tree
  const out = [], path = [];
  (function dfs(n) {
    if (!n) return;
    path.push(n.val);
    if (!n.left && !n.right) out.push(path.join('->'));
    dfs(n.left); dfs(n.right);
    path.pop();
  })(root);
  return out;
}
function maxPathSum(root) {                          // at each node: best "arm" from each side (negative -> 0)
  let best = -Infinity;
  (function gain(n) {
    if (!n) return 0;
    const l = Math.max(0, gain(n.left)), r = Math.max(0, gain(n.right));
    best = Math.max(best, n.val + l + r);          // path that BENDS at n
    return n.val + Math.max(l, r);                 // path that CONTINUES up through n
  })(root);
  return best;
}

Verified by 5 asserts

assert.equal(hasPathSum(T, 15), true);              // 1->2->5->7assert.equal(hasPathSum(T, 8), false);assert.deepEqual(allPaths(T), ['1->2->4', '1->2->5->7', '1->3->6']);assert.equal(maxPathSum(T), 24);                     // 7+5+2+1+3+6assert.equal(maxPathSum(fromLevelOrder([-3])), -3);assert.equal(hasPathSum(T, 15), true);              // 1->2->5->7
assert.equal(hasPathSum(T, 8), false);
assert.deepEqual(allPaths(T), ['1->2->4', '1->2->5->7', '1->3->6']);
assert.equal(maxPathSum(T), 24);                     // 7+5+2+1+3+6
assert.equal(maxPathSum(fromLevelOrder([-3])), -3);

Lowest Common Ancestor#

general tree (recursive) vs BST (walk by value)

function lcaGeneral(n, p, q) {                       // returns the node; p/q are values here  if (!n || n.val === p || n.val === q) return n;  const l = lcaGeneral(n.left, p, q), r = lcaGeneral(n.right, p, q);  return l && r ? n : (l ?? r);} // ═════════════════════════════════════════════════════════════════════════════// BST — everything below relies on left < node < right (no duplicates here;// say which side duplicates go if the spec allows them).// ═════════════════════════════════════════════════════════════════════════════function lcaGeneral(n, p, q) {                       // returns the node; p/q are values here
  if (!n || n.val === p || n.val === q) return n;
  const l = lcaGeneral(n.left, p, q), r = lcaGeneral(n.right, p, q);
  return l && r ? n : (l ?? r);
}

// ═════════════════════════════════════════════════════════════════════════════
// BST — everything below relies on left < node < right (no duplicates here;
// say which side duplicates go if the spec allows them).
// ═════════════════════════════════════════════════════════════════════════════

Verified by 3 asserts

assert.equal(lcaGeneral(T, 4, 7).val, 2);assert.equal(lcaGeneral(T, 4, 6).val, 1);assert.equal(lcaGeneral(T, 5, 7).val, 5);           // a node is its own ancestorassert.equal(lcaGeneral(T, 4, 7).val, 2);
assert.equal(lcaGeneral(T, 4, 6).val, 1);
assert.equal(lcaGeneral(T, 5, 7).val, 5);           // a node is its own ancestor

Search / insert / min / max#

O(h)

function bstSearch(n, v) {  while (n && n.val !== v) n = v < n.val ? n.left : n.right;  return n;}function bstInsert(n, v) {  if (!n) return new TreeNode(v);  if (v < n.val) n.left = bstInsert(n.left, v);  else if (v > n.val) n.right = bstInsert(n.right, v);  return n;                                          // duplicates ignored}const bstMin = n => { while (n.left) n = n.left; return n; };const bstMax = n => { while (n.right) n = n.right; return n; }; //             8//           /   \//          3     10//         / \      \//        1   6      14//           / \    ///          4   7  13const B = [8, 3, 10, 1, 6, 14, 4, 7, 13].reduce((root, v) => bstInsert(root, v), null);function bstSearch(n, v) {
  while (n && n.val !== v) n = v < n.val ? n.left : n.right;
  return n;
}
function bstInsert(n, v) {
  if (!n) return new TreeNode(v);
  if (v < n.val) n.left = bstInsert(n.left, v);
  else if (v > n.val) n.right = bstInsert(n.right, v);
  return n;                                          // duplicates ignored
}
const bstMin = n => { while (n.left) n = n.left; return n; };
const bstMax = n => { while (n.right) n = n.right; return n; };

//             8
//           /   \
//          3     10
//         / \      \
//        1   6      14
//           / \    /
//          4   7  13
const B = [8, 3, 10, 1, 6, 14, 4, 7, 13].reduce((root, v) => bstInsert(root, v), null);

Verified by 5 asserts

assert.deepEqual(inorder(B), [1, 3, 4, 6, 7, 8, 10, 13, 14]);   // BST inorder is sorted — THE propertyassert.equal(bstSearch(B, 7).val, 7);assert.equal(bstSearch(B, 5), null);assert.equal(bstMin(B).val, 1);assert.equal(bstMax(B).val, 14);assert.deepEqual(inorder(B), [1, 3, 4, 6, 7, 8, 10, 13, 14]);   // BST inorder is sorted — THE property
assert.equal(bstSearch(B, 7).val, 7);
assert.equal(bstSearch(B, 5), null);
assert.equal(bstMin(B).val, 1);
assert.equal(bstMax(B).val, 14);

Delete#

3 cases: leaf / one child / two children (swap with inorder successor)

function bstDelete(n, v) {  if (!n) return null;  if (v < n.val) n.left = bstDelete(n.left, v);  else if (v > n.val) n.right = bstDelete(n.right, v);  else {    if (!n.left) return n.right;                     // leaf or one child    if (!n.right) return n.left;    const succ = bstMin(n.right);                    // two children: smallest in right subtree    n.val = succ.val;    n.right = bstDelete(n.right, succ.val);  }  return n;}{  const b = structuredCloneTree(B);  bstDelete(b, 3);                                   // two children -> 3 replaced by 4  bstDelete(b, 14);                                  // one child  bstDelete(b, 1);                                   // leaf}function bstDelete(n, v) {
  if (!n) return null;
  if (v < n.val) n.left = bstDelete(n.left, v);
  else if (v > n.val) n.right = bstDelete(n.right, v);
  else {
    if (!n.left) return n.right;                     // leaf or one child
    if (!n.right) return n.left;
    const succ = bstMin(n.right);                    // two children: smallest in right subtree
    n.val = succ.val;
    n.right = bstDelete(n.right, succ.val);
  }
  return n;
}
{
  const b = structuredCloneTree(B);
  bstDelete(b, 3);                                   // two children -> 3 replaced by 4
  bstDelete(b, 14);                                  // one child
  bstDelete(b, 1);                                   // leaf
}

Verified by 4 asserts

  assert.deepEqual(inorder(b), [1, 4, 6, 7, 8, 10, 13, 14]);  assert.deepEqual(inorder(b), [1, 4, 6, 7, 8, 10, 13]);  assert.deepEqual(inorder(b), [4, 6, 7, 8, 10, 13]);  assert.equal(bstDelete(null, 1), null);  assert.deepEqual(inorder(b), [1, 4, 6, 7, 8, 10, 13, 14]);
  assert.deepEqual(inorder(b), [1, 4, 6, 7, 8, 10, 13]);
  assert.deepEqual(inorder(b), [4, 6, 7, 8, 10, 13]);
  assert.equal(bstDelete(null, 1), null);

Validate BST#

pass (lo, hi) BOUNDS down; checking only children is the classic wrong answer

function isValidBST(n, lo = -Infinity, hi = Infinity) {  if (!n) return true;  if (n.val <= lo || n.val >= hi) return false;  return isValidBST(n.left, lo, n.val) && isValidBST(n.right, n.val, hi);}// Alt: inorder traversal must be strictly increasing.function isValidBST(n, lo = -Infinity, hi = Infinity) {
  if (!n) return true;
  if (n.val <= lo || n.val >= hi) return false;
  return isValidBST(n.left, lo, n.val) && isValidBST(n.right, n.val, hi);
}
// Alt: inorder traversal must be strictly increasing.

Verified by 3 asserts

assert.equal(isValidBST(B), true);assert.equal(isValidBST(fromLevelOrder([5, 1, 4, null, null, 3, 6])), false);   // 3 is under 5's right but < 5assert.equal(isValidBST(fromLevelOrder([5, 4, 6, null, null, 3, 7])), false);  // children-only check would pass thisassert.equal(isValidBST(B), true);
assert.equal(isValidBST(fromLevelOrder([5, 1, 4, null, null, 3, 6])), false);   // 3 is under 5's right but < 5
assert.equal(isValidBST(fromLevelOrder([5, 4, 6, null, null, 3, 7])), false);  // children-only check would pass this

Kth smallest / inorder successor / closest / range sum / two-sum#

all use "inorder is sorted"

function kthSmallest(root, k) {                      // iterative inorder, stop at k  const stack = [];  let cur = root;  while (cur || stack.length) {    while (cur) { stack.push(cur); cur = cur.left; }    cur = stack.pop();    if (--k === 0) return cur.val;    cur = cur.right;  }  return null;}function inorderSuccessor(root, v) {                 // smallest value > v; remember last "went left" node  let succ = null;  for (let n = root; n;) {    if (v < n.val) { succ = n; n = n.left; } else n = n.right;  }  return succ;}function closestValue(root, target) {  let best = root.val;  for (let n = root; n;) {    if (Math.abs(n.val - target) < Math.abs(best - target)) best = n.val;    n = target < n.val ? n.left : n.right;  }  return best;}function rangeSumBST(n, lo, hi) {                    // prune subtrees outside the range  if (!n) return 0;  if (n.val < lo) return rangeSumBST(n.right, lo, hi);  if (n.val > hi) return rangeSumBST(n.left, lo, hi);  return n.val + rangeSumBST(n.left, lo, hi) + rangeSumBST(n.right, lo, hi);}function twoSumBST(root, target) {                   // inorder -> sorted array -> two pointers (or a Set during DFS)  const a = inorder(root);  for (let i = 0, j = a.length - 1; i < j;) {    const s = a[i] + a[j];    if (s === target) return true;    s < target ? i++ : j--;  }  return false;}function lcaBST(n, p, q) {                           // walk down while both on the same side  while (n) {    if (p < n.val && q < n.val) n = n.left;    else if (p > n.val && q > n.val) n = n.right;    else return n;  }  return null;}function kthSmallest(root, k) {                      // iterative inorder, stop at k
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    if (--k === 0) return cur.val;
    cur = cur.right;
  }
  return null;
}
function inorderSuccessor(root, v) {                 // smallest value > v; remember last "went left" node
  let succ = null;
  for (let n = root; n;) {
    if (v < n.val) { succ = n; n = n.left; } else n = n.right;
  }
  return succ;
}
function closestValue(root, target) {
  let best = root.val;
  for (let n = root; n;) {
    if (Math.abs(n.val - target) < Math.abs(best - target)) best = n.val;
    n = target < n.val ? n.left : n.right;
  }
  return best;
}
function rangeSumBST(n, lo, hi) {                    // prune subtrees outside the range
  if (!n) return 0;
  if (n.val < lo) return rangeSumBST(n.right, lo, hi);
  if (n.val > hi) return rangeSumBST(n.left, lo, hi);
  return n.val + rangeSumBST(n.left, lo, hi) + rangeSumBST(n.right, lo, hi);
}
function twoSumBST(root, target) {                   // inorder -> sorted array -> two pointers (or a Set during DFS)
  const a = inorder(root);
  for (let i = 0, j = a.length - 1; i < j;) {
    const s = a[i] + a[j];
    if (s === target) return true;
    s < target ? i++ : j--;
  }
  return false;
}
function lcaBST(n, p, q) {                           // walk down while both on the same side
  while (n) {
    if (p < n.val && q < n.val) n = n.left;
    else if (p > n.val && q > n.val) n = n.right;
    else return n;
  }
  return null;
}

Verified by 15 asserts

assert.equal(kthSmallest(B, 3), 4);assert.equal(kthSmallest(B, 1), 1);assert.equal(kthSmallest(B, 99), null);assert.equal(inorderSuccessor(B, 7).val, 8);assert.equal(inorderSuccessor(B, 8).val, 10);assert.equal(inorderSuccessor(B, 4).val, 6);assert.equal(inorderSuccessor(B, 14), null);assert.equal(closestValue(B, 12), 13);assert.equal(closestValue(B, 2), 3);                 // tie (3 vs 1) -> first seen on the walk wins; spec decidesassert.equal(rangeSumBST(B, 4, 10), 35);             // 4+6+7+8+10assert.equal(twoSumBST(B, 11), true);                // 4+7assert.equal(twoSumBST(B, 100), false);assert.equal(lcaBST(B, 1, 7).val, 3);assert.equal(lcaBST(B, 1, 14).val, 8);assert.equal(lcaBST(B, 13, 14).val, 14);assert.equal(kthSmallest(B, 3), 4);
assert.equal(kthSmallest(B, 1), 1);
assert.equal(kthSmallest(B, 99), null);
assert.equal(inorderSuccessor(B, 7).val, 8);
assert.equal(inorderSuccessor(B, 8).val, 10);
assert.equal(inorderSuccessor(B, 4).val, 6);
assert.equal(inorderSuccessor(B, 14), null);
assert.equal(closestValue(B, 12), 13);
assert.equal(closestValue(B, 2), 3);                 // tie (3 vs 1) -> first seen on the walk wins; spec decides
assert.equal(rangeSumBST(B, 4, 10), 35);             // 4+6+7+8+10
assert.equal(twoSumBST(B, 11), true);                // 4+7
assert.equal(twoSumBST(B, 100), false);
assert.equal(lcaBST(B, 1, 7).val, 3);
assert.equal(lcaBST(B, 1, 14).val, 8);
assert.equal(lcaBST(B, 13, 14).val, 14);

Sorted array -> balanced BST (pick the middle, recurse)#

O(n)

function sortedArrayToBST(a, lo = 0, hi = a.length - 1) {  if (lo > hi) return null;  const mid = lo + ((hi - lo) >> 1);  return new TreeNode(a[mid], sortedArrayToBST(a, lo, mid - 1), sortedArrayToBST(a, mid + 1, hi));}const S = sortedArrayToBST([1, 2, 3, 4, 5, 6, 7]);function sortedArrayToBST(a, lo = 0, hi = a.length - 1) {
  if (lo > hi) return null;
  const mid = lo + ((hi - lo) >> 1);
  return new TreeNode(a[mid], sortedArrayToBST(a, lo, mid - 1), sortedArrayToBST(a, mid + 1, hi));
}
const S = sortedArrayToBST([1, 2, 3, 4, 5, 6, 7]);

Verified by 4 asserts

assert.equal(S.val, 4);assert.equal(maxDepth(S), 3);assert.equal(isValidBST(S) && isBalanced(S), true);assert.deepEqual(inorder(S), [1, 2, 3, 4, 5, 6, 7]);assert.equal(S.val, 4);
assert.equal(maxDepth(S), 3);
assert.equal(isValidBST(S) && isBalanced(S), true);
assert.deepEqual(inorder(S), [1, 2, 3, 4, 5, 6, 7]);

Build from preorder + inorder#

preorder[0] is root; inorder splits L/R

function buildTree(pre, ino) {  const idx = new Map(ino.map((v, i) => [v, i]));  let p = 0;  return (function build(lo, hi) {    if (lo > hi) return null;    const node = new TreeNode(pre[p++]);    const m = idx.get(node.val);    node.left = build(lo, m - 1);                    // left FIRST — preorder pointer depends on it    node.right = build(m + 1, hi);    return node;  })(0, ino.length - 1);}// (postorder + inorder: root is postorder.at(-1); build RIGHT first walking backwards.)function buildTree(pre, ino) {
  const idx = new Map(ino.map((v, i) => [v, i]));
  let p = 0;
  return (function build(lo, hi) {
    if (lo > hi) return null;
    const node = new TreeNode(pre[p++]);
    const m = idx.get(node.val);
    node.left = build(lo, m - 1);                    // left FIRST — preorder pointer depends on it
    node.right = build(m + 1, hi);
    return node;
  })(0, ino.length - 1);
}
// (postorder + inorder: root is postorder.at(-1); build RIGHT first walking backwards.)

Verified by 1 assert

assert.deepEqual(toLevelOrder(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])), [3, 9, 20, null, null, 15, 7]);assert.deepEqual(toLevelOrder(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])), [3, 9, 20, null, null, 15, 7]);

Serialize / deserialize#

preorder with '#' for null; a queue rebuilds it

const serialize = root => {  const out = [];  (function go(n) { if (!n) return out.push('#'); out.push(String(n.val)); go(n.left); go(n.right); })(root);  return out.join(',');};const deserialize = s => {  const tokens = s.split(',');  let i = 0;  return (function go() {    const t = tokens[i++];    if (t === '#') return null;    return new TreeNode(Number(t), go(), go());  })();};const serialize = root => {
  const out = [];
  (function go(n) { if (!n) return out.push('#'); out.push(String(n.val)); go(n.left); go(n.right); })(root);
  return out.join(',');
};
const deserialize = s => {
  const tokens = s.split(',');
  let i = 0;
  return (function go() {
    const t = tokens[i++];
    if (t === '#') return null;
    return new TreeNode(Number(t), go(), go());
  })();
};

Verified by 3 asserts

assert.equal(serialize(fromLevelOrder([1, 2, 3, null, null, 4, 5])), '1,2,#,#,3,4,#,#,5,#,#');assert.deepEqual(toLevelOrder(deserialize(serialize(T))), toLevelOrder(T));assert.equal(serialize(null), '#');assert.equal(serialize(fromLevelOrder([1, 2, 3, null, null, 4, 5])), '1,2,#,#,3,4,#,#,5,#,#');
assert.deepEqual(toLevelOrder(deserialize(serialize(T))), toLevelOrder(T));
assert.equal(serialize(null), '#');

Flatten to linked list (preorder, via right pointers)#

reverse-postorder trick

function flatten(root) {  let prev = null;  (function go(n) {    if (!n) return;    go(n.right); go(n.left);    n.right = prev; n.left = null; prev = n;  })(root);  return root;}function flatten(root) {
  let prev = null;
  (function go(n) {
    if (!n) return;
    go(n.right); go(n.left);
    n.right = prev; n.left = null; prev = n;
  })(root);
  return root;
}

Verified by 1 assert

assert.deepEqual(toLevelOrder(flatten(fromLevelOrder([1, 2, 5, 3, 4, null, 6]))), [1, null, 2, null, 3, null, 4, null, 5, null, 6]);assert.deepEqual(toLevelOrder(flatten(fromLevelOrder([1, 2, 5, 3, 4, null, 6]))), [1, null, 2, null, 3, null, 4, null, 5, null, 6]);

N-ary trees: node.children = []; every traversal above is identical with#

//        `for (const c of n.children)` replacing left/right. Say "generalizes to N-ary".//        `for (const c of n.children)` replacing left/right. Say "generalizes to N-ary".