Day 37 — Revision: Trees basics

Revision day · trees · recursive thinking

Tonight's goal: rebuild tree basics from one focus line — answer for a node = f(answers of children).

Tonight's protocol

Use the revision-day protocol: blank file, no hints, and only the first or second run counts.

  1. 0:00-0:03 — Do the warm-up MCQs below. If one feels shaky, mark that topic as weak.
  2. 0:03-0:05 — Pick your 3 weakest problems from the menu. Open a blank file for the first one.
  3. 0:05-0:22 — Problem 1: say the pattern, base case, combine step, and complexity; then code with no hints.
  4. 0:22-0:39 — Problem 2: same rules. Stop after the first or second run and record the result.
  5. 0:39-0:56 — Problem 3: same rules. For BFS, say the queue boundary before coding.
  6. 0:56-1:03 — Compare only failed attempts. Write one WA: <root cause> line for each miss.

The problem menu

Pick your 3 weakest from this menu. Re-solve from a blank file, no hints, no stored code.

ProblemPattern name
Inorder TraversalRecursive inorder traversal
Maximum DepthTree recursion with return value
Same TreeSimultaneous DFS / lockstep comparison
Level Order TraversalBFS levels with queue snapshot
Diameter of Binary TreePiggyback on height
Balanced Binary TreePiggyback on height

Warm-up MCQs

1. Which order is inorder traversal?

2. For maximum depth, what should a real node return?

3. Spot the Same Tree bug:

if not p or not q:
    return True

4. What separates one BFS level from the next?

5. What travels upward beside height in Diameter and Balanced?

6. Which check belongs in Balanced Binary Tree?

Self-check gate

Pass tonight if at least 2 of your 3 blank-file attempts pass on run one or two, and you can say the invariant before each solution.

Failure path: if a problem fails after two runs, write WA: <root cause>, add that failed problem to the next revision, and ask your teacher with the code plus the invariant you tried to use.