DAY 21 / 30 · WEEK 3 REVIEW

Week 3 Review

Goal of the day

• Connect Days 15–20 into one decision process: given a new problem, know which access pattern it actually needs — LIFO, FIFO, pointer-chain, level-by-level, or sorted-order — before picking a data structure.
• Solve 5 mixed practice problems that draw on more than one Week 3 idea at once.
• Walk away with a one-page cheat sheet of every Week 3 template and complexity.

Concept

Week 3 looks like six separate topics, but almost every one of them is answering the same underlying question: what's the cheapest way to add or remove exactly where this problem needs it? A linked list (Day 15/16) buys O(1) insert/delete at a known pointer, when an array's O(n) shift would be too slow — and its fast/slow-pointer trick turns "find the middle" or "detect a cycle" into a single pass with no extra memory. A stack (Day 17) is the natural fit whenever the rule is "deal with the most recently opened thing first" — matching brackets, undo, backtracking. A queue or deque (Day 18) is the mirror image: oldest goes first, or (for a deque) both ends need to move. Trees (Day 19) don't have one traversal order — BFS and DFS are the exact same "explore the frontier" idea, just fed into a queue (level by level) or a stack (full depth before backtracking). A binary search tree (Day 20) is a tree with one extra invariant — everything left of a node is smaller, everything right is bigger, at every level, not just the immediate children — which is what turns search/insert into O(h) and makes an inorder walk come out already sorted.

That last connection is worth sitting with: Day 20 validated a BST by tracking a shrinking min/max bound down each recursive call. There's a completely different way to prove the exact same thing, using this week's other big idea instead of recursion — walk the tree inorder with an explicit stack (Day 17's tool, not the call stack) and confirm every value that comes out is strictly bigger than the last one you saw. If that's ever not true, the tree isn't a valid BST — no bounds tracking required, because a valid BST's inorder sequence is the sorted order, by definition. Today's visualization builds exactly that.

Diagram: which Week 3 structure do I reach for?

Interactive visualization: validating a BST with an explicit stack, no bounds tracking

Same 7-node BST as Day 20. Walk it inorder using an explicit stack (Day 17's tool) instead of recursion. Every value popped off the stack must be strictly bigger than the last one popped — that single running check is the whole BST validation, because a valid BST's inorder sequence is always sorted.

Dry run: iterative inorder validate, the valid tree (20/30/40/50/60/70/80)

Every pop was strictly bigger than the one before it — 20, 30, 40, 50, 60, 70, 80 — so the whole tree is confirmed valid. No min/max bound was ever tracked; the stack's LIFO order plus one running comparison did all the work.

Week 3 cheat sheet — code templates

// LINKED LIST (Day 15/16) — Node + insert at head, O(1)
class Node {
  constructor(val) { this.val = val; this.next = null; }
}
function insertAtHead(head, val) {
  const node = new Node(val);
  node.next = head;
  return node; // new head
}

// FAST/SLOW POINTERS (Day 16) — find the middle in one pass
function middleNode(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow; // middle (or 2nd middle on even length)
}

// STACK (Day 17) — plain array, push/pop at the END, O(1) each
const stack = [];
stack.push(x);       // add to top
const top = stack.pop(); // remove from top

// QUEUE / DEQUE (Day 18) — plain array, both ends
const queue = [];
queue.push(x);        // add to back
const front = queue.shift(); // remove from front
queue.unshift(x);     // add to front (deque only)

// BFS (Day 19) — level order, uses a QUEUE
function bfs(root) {
  const order = [];
  const queue = root ? [root] : [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node.val);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return order;
}

// DFS (Day 19) — depth order, uses a STACK (explicit, no recursion)
function dfs(root) {
  const order = [];
  const stack = root ? [root] : [];
  while (stack.length > 0) {
    const node = stack.pop();
    order.push(node.val);
    if (node.right) stack.push(node.right); // push right first
    if (node.left) stack.push(node.left);   // so left pops first
  }
  return order;
}

// BST search / insert (Day 20) — O(h)
function search(root, val) {
  let curr = root;
  while (curr) {
    if (val === curr.val) return curr;
    curr = val < curr.val ? curr.left : curr.right;
  }
  return null;
}

// TODAY'S SYNTHESIS — validate a BST via iterative inorder + one stack
function isValidBSTIterative(root) {
  const stack = [];
  let curr = root;
  let prev = null; // no value seen yet
  while (curr || stack.length > 0) {
    while (curr) { stack.push(curr); curr = curr.left; } // descend all the way left
    curr = stack.pop();
    if (prev !== null && curr.val <= prev) return false;  // out of order — invalid
    prev = curr.val;
    curr = curr.right; // then explore the right subtree
  }
  return true;
}

Complexity — everything from Week 3, at a glance

Interview corner

• If you can only ask yourself one question to pick a Week 3 structure, what is it? "What order does this problem need things removed in?" Most-recent-first is a stack. Oldest-first is a queue. A specific, already-known position is a linked list pointer. Once you know the removal order, the structure almost always falls out automatically.
• How does DFS via an explicit stack differ from DFS via recursion? They visit nodes in the exact same order — recursion's call stack is a stack, just an implicit one managed by the language runtime instead of an array you control. The explicit version exists because very deep trees can blow the real call stack (a stack overflow, Day 9's exact failure mode), and because some interviewers specifically want to see you reason about the mechanism, not just call a recursive helper.
• Why does an iterative inorder walk validate a BST without tracking min/max bounds? Because a valid BST's inorder sequence is defined to come out sorted — that's what the invariant means. Checking "is every value bigger than the last one" is mathematically the same claim as "does every node respect its full-subtree bounds," just verified through the traversal order instead of through explicit bound parameters.
  ⚠ Trap: the check must be prev !== null, not a truthy check like if (prev) — a real tree value of 0 is falsy in JavaScript but is a perfectly valid "previous value seen," and a truthy check would silently skip comparing against it.
• When does a plain array actually fall short as a queue? shift() is O(n) because every remaining element has to move down one index — fine for a small sliding window (Day 18), but a real hot-path queue at scale needs O(1) at both ends, which means a doubly linked list (or a circular buffer) under the hood instead.
  ↳ Common follow-up: "So why did Day 18 just use an array?" — the interview signal in a sliding-window problem is almost always the window-management logic itself, not whether you've hand-rolled a production-grade deque. Name the O(n) caveat out loud and move on, unless the interviewer asks you to fix it.

How to talk through it out loud: name the access pattern before the structure — "I need the most recently seen item first, so this is a stack problem" or "this needs everything at the current depth processed before going deeper, so BFS with a queue" — the same way Week 2 taught naming the constraint before naming the algorithm. When a problem visibly combines two ideas (a BST validated with a stack, a tree walked with a queue), say so explicitly — interviewers read that as recognizing structure, not stitching code together by trial and error.

5 mixed practice problems

function isPalindrome(head) {
  const vals = [];
  let node = head;
  while (node) { vals.push(node.val); node = node.next; }
  for (let i = 0, j = vals.length - 1; i < j; i++, j--) {
    if (vals[i] !== vals[j]) return false;
  }
  return true;
}

class MyStack {
  constructor() { this.q = []; }
  push(x) {
    this.q.push(x);
    for (let i = 0; i < this.q.length - 1; i++) this.q.push(this.q.shift());
  }
  pop() { return this.q.shift(); }
  top() { return this.q[0]; }
  empty() { return this.q.length === 0; }
}

function kthSmallest(root, k) {
  const stack = [];
  let curr = root;
  let count = 0;
  while (curr || stack.length > 0) {
    while (curr) { stack.push(curr); curr = curr.left; }
    curr = stack.pop();
    count++;
    if (count === k) return curr.val;
    curr = curr.right;
  }
  return -1;
}

function zigzagLevelOrder(root) {
  if (!root) return [];
  const result = [];
  let queue = [root];
  let leftToRight = true;
  while (queue.length > 0) {
    const level = [];
    const next = [];
    for (const node of queue) {
      level.push(node.val);
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    if (!leftToRight) level.reverse();
    result.push(level);
    queue = next;
    leftToRight = !leftToRight;
  }
  return result;
}

function lowestCommonAncestor(root, p, q) {
  let curr = root;
  while (curr) {
    if (p.val < curr.val && q.val < curr.val) curr = curr.left;
    else if (p.val > curr.val && q.val > curr.val) curr = curr.right;
    else return curr; // split point (or one of p/q IS curr) — this is the LCA
  }
  return null;
}

Quiz