Week 7: Trees

Pattern family: Trees · Time budget: 14 hours · Prerequisites: Weeks 1 through 6 done, with recursion and the recursion limit, nested helpers with nonlocal, and collections.deque (Week 3) fresh; you also read a ListNode fluently from Week 6. · Cold-revisit obligation: Valid Palindrome, Generate Parentheses.

Overview

A tree is the first place recursion stops being a trick and becomes the natural shape of the data. A binary tree is defined recursively (a node, a left subtree, a right subtree, each subtree itself a tree), so most tree algorithms are too: solve the subtrees, then combine. The whole skill this week is learning to think in that shape, and to separate two things that feel like one until you name them apart.

Those two things are what a recursive call returns and what it records. A traversal that asks “how deep is this subtree” can answer with a return value alone: each call returns a number to its parent. But a traversal that asks “what is the best path anywhere in this tree” cannot, because the answer it is hunting for may live entirely below the current node and never reach the root through a single return. So the recursion returns one quantity (something the parent can extend) while it records a different quantity (the best answer seen so far) into a variable that outlives any single call. Confusing the two is the single most common way tree solutions come out subtly wrong, and untangling them is the lesson of the week.

The other decision you make on every tree problem is depth-first (DFS, recursion down one path to the bottom, then back up) versus breadth-first (BFS, level by level with a queue). The cue is in the question: “path”, “depth”, “is this subtree valid” want DFS; “level by level”, “the shallowest”, “width” want BFS. Naming that choice out loud, before any code, is the move to train.

flowchart TD
    Q["Read the problem"] --> A{"Does the answer depend on<br/>going level by level, or on the<br/>shallowest thing?"}
    A -->|yes| BFS["BFS: a deque, process<br/>one full level at a time"]
    A -->|no| B{"Is it about a path, a depth,<br/>or whether a subtree has a property?"}
    B -->|yes| DFS["DFS recursion: solve subtrees,<br/>then combine"]
    B -->|"yes, but the answer can live<br/>below the current node"| RR["DFS, and split what you RETURN<br/>(for the parent) from what you<br/>RECORD (nonlocal best)"]
    B -->|no| C["Probably a different pattern.<br/>Keep reading the cues."]

Notice: the decision happens before you code, and it has two beats. First, DFS or BFS (does the answer go level by level, or down-then-up)? Second, if DFS, does the answer always travel up through a return, or can it live below a node, so you must record it separately from what you return? Naming both out loud (principle 1) is what makes this diagram fire under pressure.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the prior-week tools that trees lean on hardest.

  1. From the refresher: read this TreeNode definition aloud. What are its three attributes, and what value marks an absent child? class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right
  2. From the refresher: Python caps recursion depth near 1000 by default. On what shape of tree does a recursive traversal risk a RecursionError, and what are your two options when it does?
  3. From the refresher and Week 3: why use collections.deque and not a list for a BFS queue, and which method takes from the front?
Check your recall 1. The three attributes are `val` (the value at this node), `left` (the left child, another `TreeNode` or `None`), and `right` (the right child, another `TreeNode` or `None`). An absent child is `None`; a leaf is a node whose `left` and `right` are both `None`. You walk a tree entirely by attribute access: `node.val`, `node.left`, `node.right`. 2. A deeply unbalanced (skewed) tree, where every node has only one child, has height equal to the number of nodes, so the recursion stack is `n` deep and a large `n` overflows the default limit. Your two options: raise the limit with `import sys; sys.setrecursionlimit(...)`, or rewrite the traversal iteratively with an explicit stack. Balanced trees have height about `log n`, which never comes close to the limit. 3. A `deque` pops from the front in O(1); a `list.pop(0)` is O(n) because it shifts every remaining element left, which would turn an O(n) BFS into O(n^2). Take from the front with `popleft()`, and add to the back with `append()`.

Learning objectives

By the end of this week you can:

  • Recognize the tree cues (“path”, “depth”, “level by level”, “lowest common ancestor”, “is this a valid BST”) and reach for DFS or BFS without being told.
  • Choose DFS or BFS for a given problem and justify the choice in one sentence.
  • Distinguish what a recursive call returns (a value its parent extends) from what it records (a nonlocal best that outlives the call), and say which a given problem needs.
  • Construct a DFS recursion that solves subtrees and combines their results, and a BFS that processes a queue one full level at a time.
  • Analyze the time and space complexity of a tree traversal, naming why space is O(h) for recursion (the call stack) and what h is for balanced versus skewed trees.
  • Defend every line of each solution you commit, from memory, with no AI open, including why your base case handles None correctly.

Recognition cue

“Recursion fits the shape of the data” is the broad tell, and it is almost always true for trees. In a problem statement the surface phrases are “path from root to leaf”, “level by level” or “level order”, “the shallowest / deepest”, “lowest common ancestor”, and “is this tree balanced / symmetric / a valid BST”. The deeper tell is that the problem is defined in terms of subtrees: if the answer for a node is some combination of the answers for its children, you are looking at a DFS recursion; if the answer is about distance from the root or processing rank by rank, you are looking at a BFS.

Core concepts to internalize this week

  • The tree is recursive, so the solution usually is too. A binary tree is a node plus a left subtree plus a right subtree. The standard move is: recurse on node.left, recurse on node.right, then combine the two results with node.val. The base case is almost always if node is None, and getting that base case right (what does an empty subtree contribute?) is half the battle.
  • DFS versus BFS, and how to choose. DFS (recursion, or an explicit stack) goes deep down one path before backing up; it is the fit for path, depth, and “does this subtree have property X” questions. BFS (a deque, processing one level at a time) goes wide rank by rank; it is the fit for level-order output, the shallowest-anything, and width questions. Name the choice before you code.
  • Return versus record (the heavy idea). Some answers travel up to the caller through the return value and arrive at the root intact (depth is the clean example). Other answers can live entirely inside a subtree and never pass through the root as a single return (a best path that bends through some interior node). For the second kind, the recursion returns one quantity for the parent to use and records a different quantity into a variable that survives across calls (a nonlocal best, or class state). Keeping these two roles separate is the lesson the canonical problem exists to teach.
  • Pre-order, in-order, post-order. These name when you visit a node relative to its children. Pre-order (node, then left, then right) is natural for copying or serializing a tree top-down. In-order (left, node, right) visits a binary search tree in sorted order, which is why it is the tool for BST validation and the kth-smallest. Post-order (left, right, then node) visits children before the node, which is exactly what you need when a node’s answer is built from its children’s answers (depth, max path sum). Choosing the order is choosing when you have the information you need.
  • Serialization with explicit nulls. To turn a tree into a string and back without losing its shape, you must record where the missing children are. A traversal that writes a marker (say #) for every None captures the shape exactly; a traversal that records only the present values loses it (you cannot tell a left-only child from a right-only child). The explicit-null marker is what makes the round-trip reversible.

Common misconception. “What a tree recursion returns is the answer.” Reality. Sometimes, but not always. For depth, yes: the return value is the answer and it arrives at the root. For a best-path-anywhere problem, the answer can sit entirely below a node and never reach the root through a return; the recursion must record it into a nonlocal variable while it returns something else (a value the parent can extend). State, for every tree problem, which quantity you return and which you record. If they are the same quantity, say so on purpose; if they differ, that difference is the whole solution.

Common misconception. “The base case for a tree recursion is a leaf.” Reality. The clean base case is node is None, the empty subtree, not the leaf. If you stop at leaves you have to special-case nodes with one child (is the missing side a leaf or not?), and the logic gets tangled. Recurse straight into None and decide what an empty subtree contributes (usually 0 for a depth or a gain, or “not found” for a search). A leaf then falls out for free: it is a node whose two recursive calls both hit the None base case.

Heavy concept ahead. The return-versus-record split is the load-bearing idea of this week, so make it deliberate, in this order, on every problem where the answer can live below a node:

  1. What the recursion RETURNS. A single quantity the parent can use to build its own answer. For a path problem this is the best downward gain: the node plus the better of its two children’s gains (a straight line down, because the parent can only extend one side).
  2. What the recursion RECORDS. The best complete answer seen so far, written into a nonlocal best that outlives any one call. For a path problem this is the best path that bends through the node: the node plus the (clamped-to-nonnegative) gains from both children at once.
  3. Why they differ. A bent path cannot be returned, because a parent extending through this node can use only one side of it (a path is a line, it does not fork). So the bend is recorded and the line is returned. Write both sentences, in words, before you write code; the canonical deep-dive walks them, and the debrief checks them.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday.

  • The TreeNode class (val, left, right) and walking it by attribute access; None marks an absent child. (Refresher section 11.)
  • Recursion, and the default depth limit near 1000; import sys; sys.setrecursionlimit(...) or an explicit stack when a skewed tree is deep. (Refresher section 10.)
  • A nested helper function with nonlocal to record an answer while the helper returns something else. (Refresher section 10.)
  • collections.deque for a BFS queue: append to push the back, popleft to take the front in O(1). (Refresher section 7.)
  • Optional-style return types in your head: a search or an LCA returns “a node or None”, and you must handle the None case at every level.
  • max(...) and min(...) over a small number of candidates, and max(0, x) to clamp a negative contribution to zero.

These are tools you are allowed to know cold in an interview. The pattern (DFS or BFS, what you return versus what you record, why the base case is None) is the part you build yourself.

Pattern Card requirement

Before you solve the canonical problem, write your Pattern Card at .tutor/pattern-cards/trees.md. It must contain:

  • The recognition cue, in your own words.
  • The algorithmic skeleton in pseudocode (a DFS post-order template and a BFS level-by-level template; note where a nonlocal best would go).
  • Time and space complexity, general form (O(n) to visit every node; O(h) space for the recursion stack, where h is the height, and what h is for balanced versus skewed trees).
  • Three edge cases (the empty tree None, a single node, and a skewed tree that stresses recursion depth are good starts).
  • One war story (a bug you actually hit this week); fill this in at the end of the week.

The first four sections must be present before you start the canonical deep-dive. The tutor will probe the card; it will not write any of it for you.

Canonical deep-dive

Problem: Binary Tree Maximum Path Sum (https://leetcode.com/problems/binary-tree-maximum-path-sum/)

Binary Tree Maximum Path Sum is this course’s home for the return-versus-record split, the idea that makes a whole family of tree problems click. The full guided walk-through, with what the recursion returns, what it records, and the exact complexity, is in canonical/binary-tree-maximum-path-sum.md. Work it there. You will implement it yourself, in your own work repo, and write a short debrief. The walk-through is deliberately not an answer key: it shows you how to think, and stops short of code you could paste.

Practice set

Four problems, in this order. Each has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template. Do not skip ahead.

  1. Binary Tree Level Order Traversal (practice/binary-tree-level-order-traversal/). The canonical BFS: a queue, processing one full level per outer step. This is the problem that fixes the “process exactly one level at a time” pattern in your hands.
  2. Maximum Depth of Binary Tree (practice/maximum-depth-of-binary-tree/). The cleanest return-only DFS: the value each call returns is the answer. Solve it by recursion, then convince yourself a BFS level count gives the same number.
  3. Lowest Common Ancestor of a Binary Tree (practice/lowest-common-ancestor-of-a-binary-tree/). A DFS that returns “a node or None” and combines the two child results: where both sides report a target, you are standing on the answer.
  4. Serialize and Deserialize Binary Tree (practice/serialize-and-deserialize-binary-tree/). A design problem: build a Codec whose serialize turns a tree into a string and whose deserialize rebuilds it, with explicit null markers so the round-trip preserves the shape.

Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

  1. Pattern Card is written (you did this Monday).
  2. Name the pattern aloud and write your approach as a plain-English comment before any code.
  3. Struggle floor: 25 minutes unaided.
  4. Hint ladder if needed: six rungs, one per ask.
  5. Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

  • Explain it back: describe the difference between what a tree recursion returns and what it records to a peer who has only done arrays and linked lists, in three sentences.
  • Connect: Maximum Depth returns a value that is the answer; Maximum Path Sum returns one thing and records another. What is different about the two problems that forces that split?
  • Monitor: is it the DFS-versus-BFS choice, or the return-versus-record split, that is still fuzzy? Write the one sentence that would clear it up.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

  1. What two phrases or input shapes should make you reach for BFS rather than DFS on a tree, and what data structure does BFS need?
  2. For Maximum Path Sum, what quantity does the recursion return to its parent, and what different quantity does it record into the nonlocal best? Why can the recorded quantity not simply be returned?
  3. Why is node is None the right base case for most tree recursions, rather than stopping at a leaf?
  4. ⟲ From Week 3 and the refresher: why is collections.deque the right queue for BFS, and what is wrong with using list.pop(0)?
  5. ⟲ From the refresher: on what tree shape can a recursive traversal hit RecursionError, and what are your two ways out?
Answer key 1. "Level by level" / "level order", and "the shallowest" (minimum depth, first level where something appears) push you to BFS; width questions do too. BFS needs a queue, a `collections.deque`, from which you `popleft` the front and `append` the back. 2. It *returns* the best downward gain: `node.val` plus the larger of its two children's gains, each clamped to at least `0` (a straight line down, which the parent can extend). It *records* the best path that bends through the node: `node.val` plus *both* children's clamped gains at once. The recorded quantity cannot be returned because a path is a line, not a fork: a parent extending through this node can use only one side, so the two-sided bend ends here and must be saved separately. 3. Because stopping at `None` lets one clean base case cover every absent subtree, including the two `None` children of a leaf, so a leaf needs no special handling. Stopping at a leaf forces you to special-case nodes that have exactly one child (is the missing side a leaf or not?), which tangles the logic. 4. A `deque` pops from the front in O(1); `list.pop(0)` is O(n) because it shifts every remaining element, turning an O(n) traversal into O(n^2). Add to the back with `append`, take from the front with `popleft`. 5. A skewed (deeply unbalanced) tree, where height equals the node count, makes the recursion stack `n` deep and overflows the default limit near 1000. Two ways out: raise the limit with `sys.setrecursionlimit(...)`, or rewrite the traversal iteratively with an explicit stack.

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each. The full protocol and the two targets are in revisit.md.

  1. Valid Palindrome (Week 2, Two Pointers). A blind re-solve. Do not look at which pattern it is until you have named it yourself; recognizing it cold is the point.
  2. Generate Parentheses (Week 4, Stacks). A blind re-solve, same rules.

Neither is a tree problem, and that is deliberate: the cold revisit trains recognition across the whole course, not just this week’s pattern. Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

  • Pattern Card complete at .tutor/pattern-cards/trees.md, including the war-story field.
  • Canonical deep-dive done: Binary Tree Maximum Path Sum implemented yourself, with the return-versus-record split written out in words, plus your short debrief (in your work repo).
  • Four practice problems solved, each with a five-question debrief in its commit message.
  • .tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits, with dates.
  • .tutor/progress.md updated to “Week 7 complete; ready for Week 8.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 8 until all five are present.

Resources

Free, no account required:

  • [Article] Binary tree, the idea: https://en.wikipedia.org/wiki/Binary_tree
  • [Article] Tree traversal (pre/in/post-order, BFS): https://en.wikipedia.org/wiki/Tree_traversal
  • [Article] Breadth-first search: https://en.wikipedia.org/wiki/Breadth-first_search
  • [Docs] Python collections.deque: https://docs.python.org/3/library/collections.html#collections.deque
  • [Docs] Python recursion limit (sys.setrecursionlimit): https://docs.python.org/3/library/sys.html#sys.setrecursionlimit

Table of contents