Tree Depth-First Search

// The three depth-first orders differ only in WHEN a node does its work relative to its children.
export function traversals(root) {
  const pre = [];
  const inorder = [];
  const post = [];
  const dfs = (node) => {
    if (node === null) return;
    pre.push(node.val);       // before the children: top-down work (pass something down)
    dfs(node.left);
    inorder.push(node.val);   // between them: on a BST this visits values in sorted order
    dfs(node.right);
    post.push(node.val);      // after both: bottom-up work (combine the children's answers)
  };
  dfs(root);
  return { pre, inorder, post };
}

// Template 1: return a value up (post-order). Ask both subtrees for their answer, then combine at the node.
// Use it for height, size, sums, "is it balanced?": anything a node can compute from its children's answers.
export function height(root) {
  if (root === null) return 0;          // an empty subtree has height 0, so a leaf gets 1
  const left = height(root.left);
  const right = height(root.right);
  return 1 + Math.max(left, right);     // combine on the way back up
}

// Same shape, different combine. -1 means "unbalanced somewhere below", so one number carries both answers
// and the whole check stays O(n) instead of recomputing heights at every node.
export function isBalanced(root) {
  const check = (node) => {
    if (node === null) return 0;
    const left = check(node.left);
    if (left === -1) return -1;
    const right = check(node.right);
    if (right === -1 || Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right);
  };
  return check(root) !== -1;
}

// Template 2: carry state down (pre-order). Each call receives what its ancestors know (the max so far, a running
// sum, the allowed range) and hands an updated value to its children. Primitives are copied, so nothing to undo.
export function goodNodes(root) {
  // A node is "good" when nothing on the path from the root down to it is larger than it.
  const dfs = (node, maxSoFar) => {
    if (node === null) return 0;
    const good = node.val >= maxSoFar ? 1 : 0;
    const nextMax = Math.max(maxSoFar, node.val);
    return good + dfs(node.left, nextMax) + dfs(node.right, nextMax);
  };
  return dfs(root, -Infinity);
}

// Carrying a whole path down: push before recursing, pop after (backtracking), copy it only at a leaf.
export function rootToLeafPaths(root) {
  const paths = [];
  const path = [];
  const dfs = (node) => {
    if (node === null) return;
    path.push(node.val);
    if (node.left === null && node.right === null) paths.push([...path]); // copy: path keeps changing
    dfs(node.left);
    dfs(node.right);
    path.pop();                                                           // undo before returning to the parent
  };
  dfs(root);
  return paths;
}

// Template 3: return one thing up, record another in a variable outside the recursion.
// Longest path whose nodes all share one value, counted in edges. A path may bend at a node (left arm + right arm),
// but a parent can extend only ONE arm, so the helper returns the longer arm and the bent path goes into `best`.
export function longestUnivaluePath(root) {
  let best = 0;
  const arm = (node) => {
    if (node === null) return 0;
    const left = arm(node.left);
    const right = arm(node.right);
    const leftArm = node.left !== null && node.left.val === node.val ? left + 1 : 0;
    const rightArm = node.right !== null && node.right.val === node.val ? right + 1 : 0;
    best = Math.max(best, leftArm + rightArm); // the best path that bends exactly here
    return Math.max(leftArm, rightArm);        // what the parent is allowed to extend
  };
  arm(root);
  return best;
}

// BST template: in a binary search tree every value in a left subtree is smaller than the node and every value in a
// right subtree is larger. So one comparison tells you which whole subtree can't contain what you want: skip it.
export function rangeSum(root, low, high) {
  if (root === null) return 0;
  if (root.val < low) return rangeSum(root.right, low, high);  // root and its entire left subtree are too small
  if (root.val > high) return rangeSum(root.left, low, high);  // root and its entire right subtree are too large
  return root.val + rangeSum(root.left, low, high) + rangeSum(root.right, low, high);
}

// Walking down one branch needs no recursion at all: O(height).
export function searchBST(root, target) {
  let node = root;
  while (node !== null && node.val !== target) node = target < node.val ? node.left : node.right;
  return node;
}

// Iterative DFS: an explicit stack replaces the call stack. Same visiting order, no recursion depth limit.
export function preorderIterative(root) {
  const out = [];
  const stack = root ? [root] : [];
  while (stack.length) {
    const node = stack.pop();
    out.push(node.val);
    if (node.right) stack.push(node.right); // pushed first, so it is popped AFTER the left subtree
    if (node.left) stack.push(node.left);
  }
  return out;
}

// In-order: slide left as far as possible, visit, then step into the right subtree. Sorted order on a BST.
export function inorderIterative(root) {
  const out = [];
  const stack = [];
  let node = root;
  while (node !== null || stack.length) {
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    out.push(node.val);
    node = node.right;
  }
  return out;
}

// Post-order: run pre-order with the children swapped (node, right, left), then reverse it (left, right, node).
export function postorderIterative(root) {
  const out = [];
  const stack = root ? [root] : [];
  while (stack.length) {
    const node = stack.pop();
    out.push(node.val);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return out.reverse();
}