Day 21: Week 3 Review — 30 Days of DSA in JavaScript

DAY 21 / 30 · 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.

Iterative inorder with explicit stack — walk left, pop and compare, explore right. Every pop must be strictly bigger than the last.

Press Play or Step to begin.

Step 0 / 100

▶ Play⏭ Step↺ Reset🔀 Shuffle

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

Action	Stack (bottom → top)	Popped	prev → curr check
Descend left from 50	50, 30, 20	—	—
Pop	50, 30	20	prev=null → OK, prev=20
No right child; pop	50	30	30 > 20 → OK, prev=30
Descend right of 30, then left	50, 40	—	—
Pop	50	40	40 > 30 → OK, prev=40
No right child; pop	(empty)	50	50 > 40 → OK, prev=50
Descend right of 50, then left	70, 60	—	—
Pop	70	60	60 > 50 → OK, prev=60
No right child; pop	(empty)	70	70 > 60 → OK, prev=70
Descend right of 70	80	—	—
Pop	(empty)	80	80 > 70 → OK, prev=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

Operation	Time	Space	Note
Linked list insert/delete at a known node (Day 15/16)	O(1)	O(1)	No shifting — only pointers change. Finding that node first is O(n).
Fast/slow middle or cycle detection (Day 16)	O(n)	O(1)	One pass, two pointers — no extra data structure needed.
Stack push/pop/top (Day 17)	O(1) each	O(n)	Array’s built-in push/pop are already O(1) — no shifting at the end.
Queue enqueue/dequeue via array (Day 18)	O(1) push, O(n) shift	O(n)	push() is O(1); shift() re-indexes every remaining element — a real linked-list-backed queue avoids this.
BFS / DFS traversal (Day 19)	O(V + E)	O(V)	Every node enqueued/pushed and processed exactly once; space is the widest frontier (BFS) or deepest path (DFS).
BST search / insert (Day 20)	O(h)	O(1) iterative	h = tree height — O(log n) if balanced, degrades to O(n) if skewed (Day 20’s sorted-insert trap).
Iterative inorder BST validate (today)	O(n)	O(h)	Every node is pushed and popped exactly once; the stack never holds more than one root-to-leaf path at a time.

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

1. Palindrome Linked List

Easy — LeetCode: Palindrome Linked List

Given the head of a singly linked list, determine if it reads the same forward and backward. Combines Day 15’s list walk with Day 16’s fast/slow-pointer instinct.

Show hint

The simplest correct approach: walk the whole list once, collect every value into an array, then check the array reads the same forwards/backwards with two pointers closing in from both ends — no need to reverse anything in place for this to be correct.

Show solution

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;
}

2. Implement Stack using Queues

Easy — LeetCode: Implement Stack using Queues

Implement a LIFO stack using only queue operations (push to back, pop from front). The mirror image of Day 18’s Implement Queue using Stacks.

Show hint

After enqueuing the new element, rotate the queue by dequeuing and re-enqueuing every older element behind it — that puts the newest element back at the front, which is exactly what “top of stack” needs to read from.

Show solution

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; }
}

3. Kth Smallest Element in a BST

Medium — LeetCode: Kth Smallest Element in a BST

Given a BST, find the kth smallest value. Today’s exact iterative-inorder-with-a-stack technique, stopping early instead of walking the whole tree.

Show hint

Reuse today’s exact traversal shape. Instead of comparing each pop to the previous value, just count pops — the kth pop is the kth smallest, by the same “inorder is sorted” guarantee.

Show solution

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;
}

4. Binary Tree Zigzag Level Order Traversal

Medium — LeetCode: Binary Tree Zigzag Level Order Traversal

Return level-order traversal, but alternate direction each level (left→right, then right→left, and so on). Day 19’s BFS-with-a-queue, plus one direction flip per level.

Show hint

Run ordinary level-order BFS exactly like Day 19 — collect each level into its own array using a queue. The only new step: reverse that level’s array before adding it to the result whenever the current level is right-to-left.

Show solution

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;
}

5. Lowest Common Ancestor of a Binary Search Tree

Medium — LeetCode: Lowest Common Ancestor of a Binary Search Tree

Given a BST and two of its nodes, find their lowest common ancestor. The BST invariant (Day 20) turns a generic-tree LCA problem — which needs a stack/recursion to search both subtrees — into a single O(h) walk with no backtracking at all.

Show hint

At each node, compare both target values to the current node’s value. If both are smaller, the answer is entirely in the left subtree; if both are bigger, entirely in the right. The first node where they DON’T both go the same way is the split point — that’s the LCA, no need to ever backtrack.

Show solution

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

Question 1

Which Week 3 structure fits “process the most recently seen item first”?

• Stack (correct)
• Queue
• Binary Search Tree

LIFO — most-recent-first — is exactly what a stack provides. Undo, matching brackets, and DFS backtracking are all ‘deal with the last thing that happened before anything earlier’ problems.

Question 2

What’s the one structural change that turns a BFS traversal into a DFS traversal?

• Swap the frontier structure — queue becomes stack (or use recursion) (correct)
• DFS requires recursion; BFS can never use recursion
• DFS requires sorting the children first; BFS does not

BFS and DFS share the exact same ‘explore the frontier’ traversal shape — the only thing that changes is which structure holds the frontier: a queue gives level order (BFS), a stack gives depth order (DFS).

Question 3

Why can an iterative inorder walk validate a BST without tracking min/max bounds?

• A valid BST’s inorder sequence is always sorted, so one running “is this bigger than the last?” check suffices (correct)
• Because iterative code is always asymptotically faster than recursive code
• It can’t — min/max bounds are always required to validate a BST

A valid BST’s inorder traversal is defined to come out sorted. Checking that every popped value is bigger than the last one is mathematically equivalent to checking every node’s full-subtree min/max bounds — just verified through traversal order instead of explicit bound parameters.

Question 4

How many passes over a linked list does the fast/slow-pointer technique need to find the middle?

• One pass (correct)
• Two passes — one to count length, one to walk to the middle
• O(log n) passes, halving the list each time

The fast pointer moves 2 steps for every 1 the slow pointer moves, so by the time fast reaches the end, slow is exactly at the middle — all in a single pass over the list.

Question 5

Why is a plain JavaScript array a poor choice for a queue at scale?

• shift()/unshift() are O(n) — every remaining element has to be re-indexed (correct)
• Arrays can’t support push() at all
• Arrays can’t hold unsorted data

Array shift()/unshift() are O(n) because every remaining element has to be moved to a new index. A real hot-path queue needs O(1) at both ends, which means a linked-list-backed (or circular-buffer) implementation instead.