// ─────────────────────────────────────────────────────────────────────────────
// TREES & BINARY SEARCH TREES
// ─────────────────────────────────────────────────────────────────────────────
// 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.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 0. 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
//          /
//         7
const T = fromLevelOrder([1, 2, 3, 4, 5, null, 6, null, null, 7]);
assert.deepEqual(toLevelOrder(T), [1, 2, 3, 4, 5, null, 6, null, null, 7]);

// ── 1. 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);
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]);

// ── 2. 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();
}
assert.deepEqual(preorderIter(T), preorder(T));
assert.deepEqual(inorderIter(T), inorder(T));
assert.deepEqual(postorderIter(T), postorder(T));
assert.deepEqual(inorderIter(null), []);

// ── 3. 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));
}
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), []);

// ── 4. 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]);
assert.deepEqual(rightSideView(T), [1, 3, 6, 7]);
assert.deepEqual(leftSideView(T), [1, 2, 4, 7]);

// 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)
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]]);

// 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());
}
assert.deepEqual(boundary(T), [1, 2, 4, 7, 6, 3]);
assert.deepEqual(boundary(fromLevelOrder([1])), [1]);

// ── 5. Depth / height / size family  —  all O(n)
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;
}
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);

// ── 6. 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));
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);

// ── 7. 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;
}
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);

// ── 8. 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);
}
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 ancestor

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

// ── 9. 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  13
const B = [8, 3, 10, 1, 6, 14, 4, 7, 13].reduce((root, v) => bstInsert(root, v), null);
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);

// ── 10. 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
  assert.deepEqual(inorder(b), [1, 4, 6, 7, 8, 10, 13, 14]);
  bstDelete(b, 14);                                  // one child
  assert.deepEqual(inorder(b), [1, 4, 6, 7, 8, 10, 13]);
  bstDelete(b, 1);                                   // leaf
  assert.deepEqual(inorder(b), [4, 6, 7, 8, 10, 13]);
  assert.equal(bstDelete(null, 1), null);
}

// ── 11. 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);
}
assert.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
// Alt: inorder traversal must be strictly increasing.

// ── 12. 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;
}
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);

// ── 13. 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]);
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]);

// ── 14. 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);
}
assert.deepEqual(toLevelOrder(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])), [3, 9, 20, null, null, 15, 7]);
// (postorder + inorder: root is postorder.at(-1); build RIGHT first walking backwards.)

// ── 15. 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());
  })();
};
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), '#');

// ── 16. 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;
}
assert.deepEqual(toLevelOrder(flatten(fromLevelOrder([1, 2, 5, 3, 4, null, 6]))), [1, null, 2, null, 3, null, 4, null, 5, null, 6]);

// ── 17. 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".

console.log('ok: algorithms/trees-bst.js');