INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS
01
00/24
01 / COVER STEP 13 · BINARY TREES
INVARIANT · STEP 13 · DECK 2 OF 3
READ THE SHAPE

Deck 1 gave you the walks; this deck turns them into answers. Most problems are one postorder that returns a value or one level-batched BFS.

24Problems
5Families
17Units
19Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 24 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

DEPTH & BOTTOM-UP · 04
STRUCTURE · 05
VIEWS BY LEVEL · 05
PATHS · 07
ANCESTORS · 03
SOLVED HAS A LEETCODE LINK
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
03 / MECHANISM UNIT 01 · MAXIMUM DEPTH

POSTORDER. BOTH SUBTREES FIRST, THEN THE NODE

Left → right → root. Record a node after both its children, so the root comes last. Heights, sizes and deleting a tree all need this order.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
04 / DRILL UNIT 01 · Maximum Depth

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why is computing a node's height a postorder (children-first) operation?

The parent needs its children's answers. 1 + max(leftH, rightH) waits for both calls: that is postorder.

DRILL 02 · TRACE

A root with a left child that is a single leaf, and a right child that has one child (a chain of 2). What's the max depth (number of nodes on the longest root-to-leaf path)?

3. The right path has 3 nodes: root, child, grandchild. LeetCode counts nodes.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
05 / PROBLEM #01 · DEPTH · EASY

Maximum Depth of Binary Tree

EASY depth ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Maximum depth / height of the tree.” The base case of the whole bottom-up family.

INTUITION

A node's depth is 1 plus the deeper of its two children. Recurse; an empty subtree is 0.

STEPS
  1. maxDepth(node): if node is null, return 0
  2. left = maxDepth(node->left); right = maxDepth(node->right)
  3. return 1 + max(left, right)
↕ SCROLL
// Height = 1 + the taller subtree; empty = 0.
int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
TIMEO(n)each node visited once
SPACEO(h)recursion depth = height
TRAP

Nodes or edges. LeetCode counts nodes: an empty tree is 0, one node is 1.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
06 / MECHANISM UNIT 02 · BALANCED TREE

A NODE CANNOT ANSWER BEFORE ITS CHILDREN DO

A node can't know its height until both children report, which forces postorder. The balance check rides along free. Balanced means every node, not just the root.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
07 / DRILL UNIT 02 · Balanced Tree · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

What makes the O(n) balanced check faster than the naive one?

One combined pass instead of a height() call per node. The balance test sits inside the height recursion, so every node is visited once.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
08 / PROBLEM #02 · DEPTH · EASY

Balanced Binary Tree

EASY depth ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Is the tree height-balanced?” (every node's subtrees differ in height by ≤ 1). A height recursion with an early-exit sentinel.

INTUITION

Compute height as usual, but return −1 the instant any subtree is unbalanced; propagate −1 up so the whole check is one O(n) pass.

STEPS
  1. height(node): if null, return 0
  2. l = height(left); if l == −1, return −1
  3. r = height(right); if r == −1, return −1
  4. if abs(l − r) > 1, return −1
  5. return 1 + max(l, r); answer = height(root) != −1
↕ SCROLL
// Height helper returns -1 as an 'unbalanced below' sentinel.
int height(TreeNode* node) {
    if (node == nullptr) return 0;
    int l = height(node->left);
    if (l == -1) return -1;
    int r = height(node->right);
    if (r == -1) return -1;
    if (abs(l - r) > 1) return -1;        // unbalanced here
    return 1 + max(l, r);
}
bool isBalanced(TreeNode* root) {
    return height(root) != -1;
}
TIMEO(n)one combined height+balance pass
SPACEO(h)recursion depth
TRAP

Calling height() at every node: O(n²). Fold the check into one height pass that returns −1 once unbalanced.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
09 / DRILL UNIT 02 · Balanced Tree · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why return −1 specifically as the 'unbalanced' signal, rather than a separate boolean?

−1 can never be a real height. So it safely means 'unbalanced below', with no extra flag.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
10 / MECHANISM UNIT 03 · DIAMETER

THE ANSWER AT A NODE IS NOT WHAT THE NODE RETURNS

The longest path through a node is L + R, but it can only hand up 1 + max(L, R). Record one, return the other.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
11 / DRILL UNIT 03 · Diameter

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

At each node, what value do you RETURN to the parent, and what value do you use to UPDATE the answer?

Return height, update diameter. The parent needs this node's height; the longest path through this node is leftH + rightH.

DRILL 02 · TRACE

On the perfect (every level full) 7-node tree (root 1; 2,3; 4,5,6,7), what is the diameter in edges?

4 edges. For example 4–2–1–3–6: up from one bottom leaf to the root, down to another.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
12 / PROBLEM #03 · DEPTH · EASY

Diameter of Binary Tree

EASY depth ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Diameter, longest path between any two nodes.” The path need not pass the root, so track a global while returning heights.

INTUITION

Run the height recursion; at each node the longest bending path is leftH + rightH. Update a global max with it.

STEPS
  1. global best = 0
  2. height(node): if null, return 0
  3. l = height(left); r = height(right)
  4. best = max(best, l + r) // path bending here (edges)
  5. return 1 + max(l, r); answer = best
↕ SCROLL
// Return height; update the global diameter with leftH + rightH.
int best = 0;
int height(TreeNode* node) {
    if (node == nullptr) return 0;
    int l = height(node->left);
    int r = height(node->right);
    best = max(best, l + r);              // longest path bending at node (edges)
    return 1 + max(l, r);                 // RETURN height, not diameter
}
int diameterOfBinaryTree(TreeNode* root) {
    best = 0; height(root); return best;
}
TIMEO(n)one height pass, global updated per node
SPACEO(h)recursion depth
TRAP

Returning the diameter instead of the height. The parent needs the height; the diameter goes in a global.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
13 / MECHANISM UNIT 04 · MAXIMUM PATH SUM

A PATH MAY BEND, BUT ONLY ONCE, AND ONLY HERE

Diameter with values. A negative branch is dropped: max(0, gain). Record val + L + R, return val + max(L, R).

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
14 / DRILL UNIT 04 · Maximum Path Sum

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why do you clamp each child's returned gain with max(0, gain)?

A negative branch is worse than none. Take 0 instead of a negative gain.

DRILL 02 · RECALL

Why does the RETURNED value use max(leftGain, rightGain) while the GLOBAL update uses leftGain + rightGain?

Bend here, or keep going up. Record val + L + R; return val + max(L, R).

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
15 / PROBLEM #04 · DEPTH · HARD

Binary Tree Maximum Path Sum

HARD depth ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Maximum path sum, path may start and end anywhere.” Diameter with values, negatives allowed. Clamp and track a global.

INTUITION

Each node's best downward gain is val + max(0, better child). The best path bending at the node is val + max(0,left) + max(0,right).

STEPS
  1. global best = −infinity
  2. gain(node): if null, return 0
  3. l = max(0, gain(left)); r = max(0, gain(right)) // clamp negatives
  4. best = max(best, node->val + l + r) // bend here
  5. return node->val + max(l, r); answer = best
↕ SCROLL
// Clamp child gains to 0; track val+L+R, return val+max(L,R).
int best = INT_MIN;
int gain(TreeNode* node) {
    if (node == nullptr) return 0;
    int l = max(0, gain(node->left));    // drop a negative branch
    int r = max(0, gain(node->right));
    best = max(best, node->val + l + r); // best path bending at this node
    return node->val + max(l, r);        // a path continues up via ONE child
}
int maxPathSum(TreeNode* root) {
    best = INT_MIN; gain(root); return best;
}
TIMEO(n)one postorder, global updated per node
SPACEO(h)recursion depth
TRAP

Not clamping negatives, or starting best at 0. Drop a negative child (use 0), and start best at −∞: every value may be negative.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
16 / MECHANISM UNIT 05 · SAME TREE

TWO TREES, ONE WALK, AND STRUCTURE IS CHECKED FIRST

Walk two trees together and compare the nodes at each position. Null against non-null is already a difference.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
17 / MECHANISM UNIT 05 · SUBTREE OF ANOTHER TREE

TRY EVERY NODE AS THE ANCHOR

At every node of the big tree, run Same Tree against the pattern. It has to match all the way down to the nulls.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
18 / DRILL UNIT 05 · Same Tree · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

What are the three base/short-circuit cases when comparing two nodes p and q?

Both null: true. One null: false. Values differ: false. Pass all three and recurse on both pairs.

DRILL 02 · TRACE

The pattern is a 4 with children 1 and 2. In the big tree a 4 also has children 1 and 2, but its 2 has a left child 0. Is the pattern a subtree rooted at that 4?

No. A subtree includes every descendant, so that extra 0 makes them different.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
19 / PROBLEM #05 · COMPARE · EASY

Same Tree

EASY compare ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Are two trees identical?” Structure and values must match, a paired recursion.

INTUITION

Both null: match. One null, or different values: mismatch. Otherwise compare left with left and right with right.

STEPS
  1. isSame(p, q): if both null, return true
  2. if exactly one is null, or p->val != q->val, return false
  3. return isSame(p->left, q->left) AND isSame(p->right, q->right)
↕ SCROLL
// Compare two trees in lockstep.
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;            // both empty -> match
    if (!p || !q || p->val != q->val) return false;
    return isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}
TIMEO(n)each pair of positions visited once
SPACEO(h)recursion depth
TRAP

Mishandling the null cases. 'Both null' is a match (you reached the end together); 'exactly one null' is a mismatch (shapes differ).

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
20 / PROBLEM #19 · COMPARE · EASY

Subtree of Another Tree

EASY compare ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Is this tree a subtree of that one?” Same Tree, launched from every node.

INTUITION

Walk the big tree. At each node, run Same Tree against the pattern.

STEPS
  1. isSubtree(root, sub): if root is null, return false
  2. if same(root, sub), return true
  3. return isSubtree(root.left, sub) or isSubtree(root.right, sub)
  4. same(a, b): if either is null, return a == b
  5. return a.val == b.val and same(lefts) and same(rights)
↕ SCROLL
// Try every node of root as the anchor of a Same Tree match.
bool same(TreeNode* a, TreeNode* b) {
    if (!a || !b) return a == b;          // null against a node: different
    return a->val == b->val
        && same(a->left, b->left) && same(a->right, b->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (!root) return false;              // nowhere left to anchor
    if (same(root, subRoot)) return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
TIMEO(n · m)same() restarts at each of the n nodes and can walk m
SPACEO(h)recursion depth of the big tree
TRAP

Stopping when the pattern runs out. Extra descendants in the big tree must make the match fail.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
21 / PROBLEM #24 · COMPARE · MED

Find Duplicate Subtrees

MED compare ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Return every subtree that appears more than once.” Give each subtree a key, and count the keys.

INTUITION

Give each distinct subtree an id. Its key is (value, left id, right id). A key seen twice is a duplicate.

STEPS
  1. dfs(node) returns an id for the subtree; a null returns 0
  2. key = (node.val, id of left, id of right)
  3. if the key is new, give it the next id
  4. count[id]++; when it reaches 2, add node to the answer
  5. return id
BRUTEO(n²)
→
OPTIMALO(n)
↕ SCROLL
// Give every distinct subtree an id; a subtree is (value, left id, right id).
unordered_map<string, int> ids;           // key -> id
unordered_map<int, int> seen;             // id -> how many times
vector<TreeNode*> res;
int dfs(TreeNode* node) {
    if (!node) return 0;                  // every empty subtree is id 0
    int l = dfs(node->left), r = dfs(node->right);
    string key = to_string(node->val) + "," + to_string(l) + "," + to_string(r);
    if (!ids.count(key)) { int fresh = ids.size() + 1; ids[key] = fresh; }
    int id = ids[key];
    if (++seen[id] == 2) res.push_back(node);    // the second sighting only
    return id;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    dfs(root);
    return res;
}
TIMEO(n)each node builds one constant-size key
SPACEO(n)one id and one count per distinct subtree
TRAP

Writing the whole subtree out as the key. Correct, but a chain builds O(n²) characters.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
22 / DRILL UNIT 05 · Same Tree · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

A subtree's key is (value, left id, right id), and a missing child has id 0. Why must the key keep that 0?

Values alone do not fix the shape. A 1 with a left leaf 2 and a 1 with a right leaf 2 hold the same values.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
23 / MECHANISM UNIT 06 · SYMMETRIC & INVERT

SYMMETRY IS A QUESTION ABOUT A PAIR, NOT A NODE

Two pointers into one tree, paired outside with outside: (a.left, b.right) and (a.right, b.left).

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
24 / DRILL UNIT 06 · Symmetric & Invert · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

In the symmetric check, which children do you compare across the two subtrees?

Cross-pair: outer with outer, inner with inner. A mirror reflects left↔right, so the left subtree's left edge corresponds to the right subtree's right edge.

DRILL 02 · RECALL

Invert Binary Tree in one line of logic per node. What is it?

Swap children, recurse. swap(node->left, node->right) at every node flips the tree horizontally.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
25 / DRILL UNIT 06 · Symmetric & Invert · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Same Tree and Symmetric are one template. What changes between them?

Which children are paired. Same Tree pairs left with left; Symmetric pairs left with right. Invert just swaps each node's children.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
26 / PROBLEM #06 · COMPARE · EASY

Symmetric Tree

EASY compare ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Is the tree a mirror of itself?” Compare the two halves with a MIRRORED paired recursion.

INTUITION

Symmetry means the left subtree mirrors the right. Compare left.left with right.right and left.right with right.left, the cross-pairing.

STEPS
  1. isMirror(a, b): if both null, return true
  2. if exactly one null, or a->val != b->val, return false
  3. return isMirror(a->left, b->right) AND isMirror(a->right, b->left)
  4. answer = root == null OR isMirror(root->left, root->right)
↕ SCROLL
// Mirror check: cross-pair the children.
bool isMirror(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b || a->val != b->val) return false;
    return isMirror(a->left, b->right)   // OUTER pair
        && isMirror(a->right, b->left);  // INNER pair
}
bool isSymmetric(TreeNode* root) {
    return !root || isMirror(root->left, root->right);
}
TIMEO(n)each mirrored pair visited once
SPACEO(h)recursion depth
TRAP

Comparing same-side children (left.left with right.left). That checks whether the two subtrees are identical, not mirror images.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
27 / PROBLEM #07 · COMPARE · EASY

Invert Binary Tree

EASY compare ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Invert / mirror the tree.” Swap every node's two children.

INTUITION

Swap each node's left and right, then recurse into both. The result is the mirror Symmetric tests for.

STEPS
  1. invert(node): if null, return null
  2. swap(node->left, node->right)
  3. invert(node->left); invert(node->right)
  4. return node
↕ SCROLL
// Swap children at every node.
TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}
TIMEO(n)each node visited once
SPACEO(h)recursion depth
TRAP

Swapping AFTER recursing without care, or forgetting to return the root. Swap then recurse, or recurse then swap.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
28 / MECHANISM UNIT 07 · ZIG-ZAG LEVEL ORDER

LEVEL ORDER, BFS, ONE LEVEL AT A TIME, WITH A QUEUE

Row by row, with a queue. Take the front, record it, add its children at the back. They wait behind the rest of their row.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
29 / DRILL UNIT 07 · Zig-Zag Level Order

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

For zig-zag, does the way you push children onto the queue change between levels?

Children always go in left, then right. Only the output of every other level flips.

DRILL 02 · TRACE

On the 7-node tree (root 1; 2,3; 4,5,6,7), what is the zig-zag order?

1 · 3,2 · 4,5,6,7. Every other level is read right to left.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
30 / PROBLEM #08 · VIEWS · MED

Binary Tree Zigzag Level Order Traversal

MED views ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Zig-zag / spiral level order.” Level order with the direction flipped each level.

INTUITION

Size-batched BFS plus a direction flag. On a right-to-left level, fill the level list from the back.

STEPS
  1. BFS with a queue; leftToRight = true
  2. each level: read size; make a list of that size
  3. pop size nodes; index = leftToRight ? i : size−1−i; place val at that index
  4. push children left-then-right as usual; flip leftToRight
  5. append the level list to the result
↕ SCROLL
// Level order; reverse the placement on alternate levels.
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    bool leftToRight = true;
    while (!q.empty()) {
        int n = q.size();
        vector<int> level(n);
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front(); q.pop();
            int idx = leftToRight ? i : n - 1 - i;   // place, don't reorder queue
            level[idx] = node->val;
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        leftToRight = !leftToRight;
        res.push_back(level);
    }
    return res;
}
TIMEO(n)each node enqueued/dequeued once
SPACEO(w)queue holds one level
TRAP

Flipping the push order. Always enqueue left, then right. Flip only the output.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
31 / MECHANISM UNIT 08 · RIGHT VIEW & NEXT POINTERS

KEY EACH NODE, THEN DECIDE WHO KEEPS THE KEY

Level order again. Each node is keyed by its level and the last one per level wins. First wins would give the left view.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
32 / DRILL UNIT 08 · Right View & Next Pointers · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Using BFS, how do you capture the right-side view?

The last pop of each level. BFS reads a level left to right, so the last one is the rightmost.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
33 / PROBLEM #09 · VIEWS · MED

Binary Tree Right Side View

MED views ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Right side view, the rightmost node of each level.” Size-batched BFS, take the last.

INTUITION

BFS by level; the last node popped in each level is its rightmost. Record it.

STEPS
  1. BFS with a queue by level
  2. each level: read size; loop size pops, pushing children
  3. when i == size−1 (last pop of the level), append node->val to the result
  4. return the result (one value per level)
↕ SCROLL
// The last node popped in each BFS level is the rightmost.
vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front(); q.pop();
            if (i == n - 1) res.push_back(node->val);   // rightmost of level
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return res;
}
TIMEO(n)each node visited once
SPACEO(w)queue holds one level
TRAP

Following right pointers only. A node from the left subtree can be rightmost on a deep level.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
34 / PROBLEM #10 · VIEWS · MED

Populating Next Right Pointers in Each Node

MED views ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Every node has an extra pointer, next, null at first. Point it at the node to its right on the same level.

INTUITION

In a perfect tree: left.next = right, and right.next = node.next ? node.next.left : null. The level above's links do the work.

STEPS
  1. start at the root; leftmost = root
  2. while leftmost has a left child (not the last level):
  3. walk the current level via next: set node->left->next = node->right
  4. set node->right->next = node->next ? node->next->left : null
  5. advance leftmost = leftmost->left
↕ SCROLL
// Perfect tree: wire level L+1 using level L's next chain. O(1) space.
Node* connect(Node* root) {
    Node* leftmost = root;
    while (leftmost && leftmost->left) {
        Node* node = leftmost;
        while (node) {
            node->left->next = node->right;
            node->right->next = node->next ? node->next->left : nullptr;
            node = node->next;               // walk the current level
        }
        leftmost = leftmost->left;           // drop to the next level
    }
    return root;
}
TIMEO(n)each node connected once
SPACEO(1)no queue. Uses the next links being built
TRAP

Using a queue when O(1) space is expected. Wire each level from the next links of the level above.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
35 / DRILL UNIT 08 · Right View & Next Pointers · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Populating next-right pointers on a PERFECT binary tree can be done in O(1) extra space. What's the key relation?

Use the current level's next links. left.next = right; right.next = the left child of node.next, if any.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
36 / MECHANISM UNIT 09 · TOP VIEW

FIRST AT THIS DISTANCE MEANS HIGHEST

Key each node by column: root 0, left −1, right +1. Keep the first node per column. BFS makes first mean highest.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
37 / DRILL UNIT 09 · Top View

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why does a plain 'first one wins' rule need BFS, not DFS?

BFS reaches the highest node of each column first. So 'first seen' is exactly the top view.

DRILL 02 · RECALL

How is bottom view different from top view in the same framework?

Keep the last node per column. Top view keeps the first; bottom view overwrites, so the deepest stays.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
38 / MECHANISM UNIT 10 · BOTTOM VIEW

THE SAME WALK, ONE WORD DIFFERENT

Top view with the guard removed: overwrite every time, so the last, deepest node per column stays.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
39 / DRILL UNIT 10 · Bottom View

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Top view keeps the first node per column; bottom view keeps the last. Why does BFS make 'last' mean the correct node for bottom view?

Later in BFS means deeper. So the last node seen in a column is the lowest one.

DRILL 02 · RECALL

What decides the left-to-right ordering of the two views' output?

Columns from the smallest index to the largest. That reads the view left to right.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
40 / MECHANISM UNIT 11 · VERTICAL ORDER

STOP CHOOSING. KEEP THE WHOLE COLUMN

Keep every node, grouped by column. Nodes in the same row and column are ordered by value.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
41 / DRILL UNIT 11 · Vertical Order

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Two nodes land in the same column at the same row (depth). How does LeetCode's vertical order break the tie?

Same column and row: smaller value first. Sort each column by (row, value).

DRILL 02 · RECALL

How do you compute a node's column, and why does it place vertical lines correctly?

Left child: column − 1. Right child: column + 1. A column is a fixed sideways offset from the root.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
42 / PROBLEM #11 · VIEWS · HARD

Vertical Order Traversal of a Binary Tree

HARD views ▶ SOLVE ON LEETCODELC 987. Two nodes in the same row and column go in value order. LC 314 (premium) wants them left to right, so this solution fails there.
SIGNAL — WHAT GIVES IT AWAY

“Vertical order traversal.” Group nodes by column; within a column order by (row, value).

INTUITION

BFS with (row, col): left child col − 1, right child col + 1. Bucket by column, then sort each column by (row, value).

STEPS
  1. map: column → list of (row, value)
  2. BFS from (root, 0, 0); for each node push (row, val) into map[col]
  3. children: (row+1, col−1) and (row+1, col+1)
  4. for each column in sorted order, sort its list by (row, value), take the values
  5. return the columns left to right
↕ SCROLL
// BFS carrying (row, col); bucket by column, sort by (row, val).
vector<vector<int>> verticalTraversal(TreeNode* root) {
    map<int, vector<pair<int,int>>> cols;   // sorted by col; each holds (row, val)
    queue<tuple<TreeNode*,int,int>> q;     // a tuple is a pair with three parts
    q.push({root, 0, 0});
    while (!q.empty()) {
        auto [node, row, col] = q.front(); q.pop();   // unpack the three parts
        cols[col].push_back({row, node->val});
        if (node->left)  q.push({node->left,  row + 1, col - 1});
        if (node->right) q.push({node->right, row + 1, col + 1});
    }
    vector<vector<int>> res;
    for (auto& [col, vec] : cols) {   // columns come out left to right
        sort(vec.begin(), vec.end());   // pairs sort by first (row), ties by second (val)
        vector<int> colVals;
        for (auto& [row, val] : vec) colVals.push_back(val);
        res.push_back(colVals);
    }
    return res;
}
TIMEO(n log n)sorting within columns
SPACEO(n)the map of all nodes
TRAP

Missing the tie-break. Two nodes in the same column and row are ordered by value.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
43 / MECHANISM UNIT 12 · BOUNDARY TRAVERSAL

THREE PASSES, AND THE JOINS ARE THE PROBLEM

Three passes: left edge down, leaves left to right, right edge up. Keep leaves out of the edge passes, or they print twice.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
44 / DRILL UNIT 12 · Boundary Traversal

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why are leaves deliberately excluded from the left- and right-boundary walks?

So corner leaves are not counted twice. A leaf at the end of an edge belongs to the leaf pass only.

DRILL 02 · RECALL

Why is the right boundary collected bottom-up (or reversed) rather than top-down?

Anti-clockwise climbs the right side. So the right edge is emitted bottom-up.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
45 / MECHANISM UNIT 13 · MAXIMUM WIDTH

INDEX THE NODES AS IF THE TREE WERE AN ARRAY

Number each level's slots, gaps included: the children of i are 2i and 2i+1. Width = last − first + 1.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
46 / DRILL UNIT 13 · Maximum Width

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why index nodes as 2i and 2i+1 instead of just counting nodes per level?

Slot numbers count the empty positions too. Width includes the gaps, so you need positional indices, not a node tally.

DRILL 02 · RECALL

Why subtract the first index of each level from all indices on that level?

Only the differences matter. Width is last − first + 1, so re-basing keeps the numbers small and the width the same.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
47 / PROBLEM #12 · VIEWS · MED

Maximum Width of Binary Tree

MED views ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Maximum width, counting null gaps.” Number the slots; width = last − first + 1.

INTUITION

BFS carrying a slot number (children in slots 2i, 2i+1). Per level, width is the last slot minus the first plus 1.

STEPS
  1. BFS carrying (node, index); start (root, 0)
  2. each level: read size; first = index of the first node this level
  3. for each node: normIdx = index − first; children get 2*normIdx and 2*normIdx+1
  4. width = lastIndex − firstIndex + 1; track the max
  5. return the max width
↕ SCROLL
// Slot numbers; normalise per level to avoid overflow.
int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int best = 0;
    queue<pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int n = q.size();
        unsigned long long first = q.front().second, last = first;
        for (int i = 0; i < n; i++) {
            auto [node, idx] = q.front(); q.pop();
            idx -= first;                        // re-base to avoid overflow
            last = idx;
            if (node->left)  q.push({node->left,  2 * idx});
            if (node->right) q.push({node->right, 2 * idx + 1});
        }
        best = max(best, (int)(last + 1));
    }
    return best;
}
TIMEO(n)each node visited once
SPACEO(w)queue holds one level
TRAP

Index overflow. 2i+1 doubles every level. Subtract the level's first index as you go.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
48 / MECHANISM UNIT 14 · ROOT-TO-LEAF PATHS

THE POP IS THE ONLY LINE THAT MATTERS

Carry the path down and print it at each leaf. Pop on the way out, or it leaks into the sibling branch.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
49 / MECHANISM UNIT 14 · ROOT-TO-LEAF PATHS

SOME ANSWERS TRAVEL DOWN, NOT UP

Here information flows down: each call gets mx, the largest value above it. A node is good when val ≥ mx.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
50 / DRILL UNIT 14 · Root-to-Leaf Paths · 1 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

In Path Sum (root-to-leaf equals target), what is the base case, and how do you avoid a subtle bug at a node with one child?

Test only at a real leaf. At a node with one child, the null side is not a finished path.

DRILL 02 · TRACE

Count Good Nodes on one path: the root is 3, its child is 1, and that node's child is 2. Which of the three are good?

Only the 3. A node is good when no value above it on the path is larger.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
51 / DRILL UNIT 14 · Root-to-Leaf Paths · 2 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Sum Root to Leaf Numbers carries cur = cur * 10 + val down and never undoes it. Path Sum II had to pop. Why the difference?

An argument passed by value is a private copy. When a call returns, the caller's cur is untouched, so there is nothing to undo.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
52 / PROBLEM #13 · PATHS · EASY

Binary Tree Paths

EASY paths ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Print all root-to-leaf paths.” Carry the path down; record it at each leaf.

INTUITION

DFS carrying the path so far. At a leaf, record the completed path.

STEPS
  1. dfs(node, path): if null, return
  2. append node->val to path
  3. if node is a leaf (both children null): record the path string
  4. else dfs(left, path); dfs(right, path)
  5. no pop: path is passed by value, so each call's copy vanishes on return
↕ SCROLL
// Carry the path down; emit it at each leaf.
void dfs(TreeNode* node, string path,   // by value: a private copy, so no pop
         vector<string>& res) {
    if (!node) return;
    path += to_string(node->val);
    if (!node->left && !node->right) { res.push_back(path); return; }
    path += "->";
    dfs(node->left, path, res);
    dfs(node->right, path, res);
}
vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> res; dfs(root, "", res); return res;
}
TIMEO(n·h)each node visited once; building each path costs O(h)
SPACEO(h)recursion + path
TRAP

Recording at a null or a one-child node. A path ends only at a leaf.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
53 / PROBLEM #14 · PATHS · EASY

Path Sum

EASY paths ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Does a root-to-leaf path sum to the target?” Subtract on the way down; test at a leaf.

INTUITION

Recurse subtracting the node's value from the remaining target. At a leaf, success is remaining == node value.

STEPS
  1. hasPath(node, target): if null, return false
  2. if leaf (both children null): return target == node->val
  3. return hasPath(left, target − node->val) OR hasPath(right, target − node->val)
↕ SCROLL
// Root-to-leaf sum == target: subtract down, check at leaves.
bool hasPathSum(TreeNode* node, int target) {
    if (!node) return false;
    if (!node->left && !node->right) return target == node->val;
    return hasPathSum(node->left,  target - node->val)
        || hasPathSum(node->right, target - node->val);
}
TIMEO(n)each node visited once
SPACEO(h)recursion depth
TRAP

Returning true at null. An empty child is not a finished path. Test only at a real leaf.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
54 / PROBLEM #15 · PATHS · MED

Path Sum II

MED paths ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Collect all root-to-leaf paths summing to the target.” DFS with backtracking.

INTUITION

Carry the current path and remaining target. At a leaf that hits 0, record a copy of the path.

STEPS
  1. dfs(node, target, path): if null, return
  2. push node->val to path; target −= node->val
  3. if leaf and target == 0: record a copy of path
  4. else dfs(left, target, path); dfs(right, target, path)
  5. pop from path (backtrack)
↕ SCROLL
// Backtracking: push, recurse, pop; record a copy at a matching leaf.
void dfs(TreeNode* node, int target, vector<int>& path,
         vector<vector<int>>& res) {
    if (!node) return;
    path.push_back(node->val);
    target -= node->val;
    if (!node->left && !node->right && target == 0)
        res.push_back(path);                 // a copy of the current path
    else {
        dfs(node->left,  target, path, res);
        dfs(node->right, target, path, res);
    }
    path.pop_back();                         // backtrack
}
vector<vector<int>> pathSum(TreeNode* root, int target) {
    vector<vector<int>> res; vector<int> path;
    dfs(root, target, path, res); return res;
}
TIMEO(n·h)each node once; copying a matching path costs O(h)
SPACEO(h)recursion + path
TRAP

Not popping, or saving the shared path. Pop on the way out, and save a copy (Python path[:]).

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
55 / PROBLEM #22 · PATHS · MED

Sum Root to Leaf Numbers

MED paths ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Each root-to-leaf path spells a number; add them all.” Carry the number down, return it at a leaf.

INTUITION

Each step down appends a digit: cur = cur * 10 + val. Return cur at a leaf; every other node returns its children's sum.

STEPS
  1. dfs(node, cur): if node is null, return 0
  2. cur = cur * 10 + node.val
  3. if node has no children, return cur
  4. return dfs(left, cur) + dfs(right, cur)
  5. answer = dfs(root, 0)
↕ SCROLL
// Carry the number built so far down; a leaf returns it.
int dfs(TreeNode* node, int cur) {
    if (!node) return 0;                  // a missing child adds nothing
    cur = cur * 10 + node->val;           // one level down appends a digit
    if (!node->left && !node->right) return cur;
    return dfs(node->left, cur) + dfs(node->right, cur);
}
int sumNumbers(TreeNode* root) {
    return dfs(root, 0);
}
TIMEO(n)each node is visited once
SPACEO(h)recursion depth
TRAP

Returning cur at a null child. A one-child node would count a half-built number.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
56 / PROBLEM #20 · PATHS · MED

Count Good Nodes in Binary Tree

MED paths ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Count nodes with no larger value on the path from the root.” State carried down, not returned up.

INTUITION

Whether a node is good depends on what lies above it. Pass the largest value so far down as an argument.

STEPS
  1. dfs(node, mx): if node is null, return 0
  2. good = 1 if node.val >= mx else 0
  3. mx = max(mx, node.val)
  4. return good + dfs(left, mx) + dfs(right, mx)
  5. start with mx = −infinity, so the root is always good
↕ SCROLL
// Carry the largest value on the path down as an argument.
int dfs(TreeNode* node, int mx) {
    if (!node) return 0;
    int good = node->val >= mx ? 1 : 0;   // nothing above is bigger
    mx = max(mx, node->val);              // the cap for everything below
    return good + dfs(node->left, mx) + dfs(node->right, mx);
}
int goodNodes(TreeNode* root) {
    return dfs(root, INT_MIN);            // the root is always good
}
TIMEO(n)each node is visited once
SPACEO(h)the recursion or the explicit stack
TRAP

Comparing with the parent only. A grandparent can still be larger.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
57 / PROBLEM #23 · PATHS · MED

Longest ZigZag Path in a Binary Tree

MED paths ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Longest path that alternates left and right.” Carry two lengths down: arrived by a left step, arrived by a right step.

INTUITION

A zigzag grows only by a step the other way. Pass each child two lengths: ending in a left step, ending in a right step. The left child gets viaRight + 1.

STEPS
  1. dfs(node, viaLeft, viaRight): the zigzag ending here, by its last step
  2. best = max(best, viaLeft, viaRight)
  3. left child gets (viaRight + 1, 0)
  4. right child gets (0, viaLeft + 1)
  5. start with dfs(root, 0, 0); the answer is best
↕ SCROLL
// Carry down the zigzag length ending at each node, by last step.
int best = 0;
void dfs(TreeNode* node, int viaLeft, int viaRight) {
    if (!node) return;
    best = max({best, viaLeft, viaRight});
    dfs(node->left,  viaRight + 1, 0);   // step left: extends a path that arrived by a right step
    dfs(node->right, 0, viaLeft + 1);    // step right: extends a path that arrived by a left step
}
int longestZigZag(TreeNode* root) {
    best = 0;
    dfs(root, 0, 0);
    return best;
}
TIMEO(n)each node is visited once
SPACEO(h)the recursion or the explicit stack
TRAP

Extending with the same direction. Two lefts in a row restart the count at 1.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
58 / PROBLEM #16 · PATHS · MED

Path Sum III

MED paths ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Count paths (any node down to any descendant) summing to target.” Prefix-sum + hashmap.

INTUITION

Prefix sum = total from the root to a node. At node B, count the ancestors whose prefix is prefix(B) − target. Add to the map going down, remove coming back.

STEPS
  1. map prefixCount = {0: 1}; running = 0, total = 0
  2. dfs(node): if null, return
  3. running += node->val; total += prefixCount[running − target]
  4. prefixCount[running]++; dfs(left); dfs(right)
  5. prefixCount[running]-- (backtrack the map); answer = total
↕ SCROLL
// Prefix-sum count: paths ending here with sum target.
int total = 0;
void dfs(TreeNode* node, long running, long target,
         unordered_map<long,int>& seen) {
    if (!node) return;
    running += node->val;
    total += seen.count(running - target) ? seen[running - target] : 0;
    seen[running]++;
    dfs(node->left, running, target, seen);
    dfs(node->right, running, target, seen);
    seen[running]--;                          // backtrack the map
}
int pathSum(TreeNode* root, int target) {
    total = 0; unordered_map<long,int> seen{{0,1}};
    dfs(root, 0, target, seen); return total;
}
TIMEO(n)each node visited once, O(1) map ops
SPACEO(n)the prefix map + recursion
TRAP

Not undoing the prefix count. Decrement it after a node's subtrees, or one branch's sums leak into its sibling.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
59 / DRILL UNIT 14 · Root-to-Leaf Paths · 3 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Path Sum III counts paths that go downward between ANY two nodes. Why does a prefix-sum hashmap solve it in O(n)?

Prefix sums along the current path. A path ending here sums to target when an ancestor's prefix is current − target.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
60 / MECHANISM UNIT 15 · LOWEST COMMON ANCESTOR

WHERE TWO SEARCHES MEET IS THE ANSWER

Each call returns what it found. A node that hears from both sides is the LCA; every other node just passes the answer up.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
61 / DRILL UNIT 15 · Lowest Common Ancestor

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

When does a node conclude that IT is the lowest common ancestor?

One target on each side ⇒ this node is the split. It is the deepest node holding both: the LCA.

DRILL 02 · RECALL

Why does returning the node itself when node == p || node == q correctly handle the case where one target is an ancestor of the other?

The higher target is found first and returned. It is an ancestor of the other, so it is the LCA. No special case needed.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
62 / PROBLEM #17 · ANCESTORS · MED

Lowest Common Ancestor of a Binary Tree

MED ancestors ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Lowest common ancestor in a binary tree” (not a BST). One bottom-up pass.

INTUITION

Null, p or q: return the node. If both sides return something, this node is the LCA. Otherwise pass up the side that did.

STEPS
  1. lca(node, p, q): if null or node == p or node == q, return node
  2. left = lca(node->left, p, q); right = lca(node->right, p, q)
  3. if both non-null, return node // targets split here
  4. return left ? left : right
↕ SCROLL
// Both subtrees report a target -> this node is the LCA.
TreeNode* lowestCommonAncestor(TreeNode* node, TreeNode* p, TreeNode* q) {
    if (!node || node == p || node == q) return node;
    TreeNode* left  = lowestCommonAncestor(node->left, p, q);
    TreeNode* right = lowestCommonAncestor(node->right, p, q);
    if (left && right) return node;          // p and q on different sides
    return left ? left : right;              // both on one side (or neither)
}
TIMEO(n)each node visited once
SPACEO(h)recursion depth
TRAP

Steering by value. That only works in a BST. A plain tree is unordered, so search both sides.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
63 / MECHANISM UNIT 16 · NODES AT DISTANCE K

A TREE POINTS DOWN. GIVE IT EDGES THAT POINT UP

Distance K has to go up as well. Record each node's parent, then BFS from the target and stop at layer K.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
64 / DRILL UNIT 16 · Nodes at Distance K · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why can't you solve 'all nodes at distance K' with a plain downward DFS from the target?

Some answers are above or across. You must go up to the parent, then into its other subtree.

DRILL 02 · RECALL

Once you have the parent map and BFS from the target, why is a visited set essential?

Undirected edges mean you can revisit. The visited set prevents it.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
65 / PROBLEM #18 · ANCESTORS · MED

All Nodes Distance K in Binary Tree

MED ancestors ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“All nodes at distance K from a target.” Turn the tree into a graph, then BFS.

INTUITION

Distance-K nodes can be above the target. Build a parent map, then BFS from the target over left, right and parent, K layers.

STEPS
  1. pass 1: DFS/BFS to record parent[node] for every node
  2. BFS from target: queue = {target}, visited = {target}, dist = 0
  3. each layer: if dist == K, collect all queued node values and return
  4. else expand each node to left, right, parent (skip visited)
  5. dist++ per layer
↕ SCROLL
// Parent map turns the tree into a graph; BFS K layers from target.
unordered_map<TreeNode*, TreeNode*> parent;
void mark(TreeNode* n, TreeNode* p) {
    if (!n) return; parent[n] = p; mark(n->left, n); mark(n->right, n);
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
    parent.clear();
    mark(root, nullptr);
    queue<TreeNode*> q; q.push(target);
    unordered_set<TreeNode*> seen{target};   // a map with keys only: "been here?"
    int dist = 0;
    while (!q.empty()) {
        if (dist == K) {
            vector<int> res;
            while (!q.empty()) { res.push_back(q.front()->val); q.pop(); }
            return res;
        }
        int n = q.size();
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front(); q.pop();
            for (TreeNode* nb : {node->left, node->right, parent[node]})
                if (nb && !seen.count(nb)) { seen.insert(nb); q.push(nb); }
        }
        dist++;
    }
    return {};
}

// OPTIONAL · INTERVIEW FOLLOW-UP. No parent map: dfs returns the distance
// down to the target, or -1. (res, target and K are members here.)
void down(TreeNode* n, int d) {                  // collect nodes d levels below n
    if (!n) return;
    if (d == 0) { res.push_back(n->val); return; }
    down(n->left, d - 1); down(n->right, d - 1);
}
int dfs(TreeNode* n) {
    if (!n) return -1;
    if (n == target) { down(n, K); return 0; }
    int l = dfs(n->left), r = dfs(n->right);
    if (l < 0 && r < 0) return -1;               // target is not below me
    int d = (l >= 0 ? l : r) + 1;                // my distance to the target
    if (d == K) res.push_back(n->val);
    else if (d < K) down(l >= 0 ? n->right : n->left, K - d - 1);
    return d;
}
TIMEO(n)one pass to map parents, one BFS
SPACEO(n)parent map + visited set + queue
TRAP

Searching only downward, or no visited set. Go up through the parent map, and mark visited so you never loop.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
66 / DRILL UNIT 16 · Nodes at Distance K · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

An interviewer asks for Distance K without a parent map. One DFS can do it if every call returns a single number. Which number?

The distance down to the target, or −1 if it is not below. An ancestor hearing d from a child is d + 1 away.

DRILL 02 · TRACE

The target is the root's left child and K = 2. In the one-pass DFS, where does the root look for answers on its right side?

At its right child. The target returns 0, so the root is 1 away and has one step left to spend.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
67 / MECHANISM UNIT 17 · BURN THE TREE

THE SAME GRAPH, ASKED HOW LONG INSTEAD OF WHO

The same BFS as distance K, but run it until it empties and count the layers. The start costs 0 minutes, so the count begins at −1.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
68 / DRILL UNIT 17 · Burn the Tree · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why is the minimum burn time equal to the maximum distance from the start node?

The last node to burn is the farthest. Fire spreads one layer per minute.

DRILL 02 · RECALL

What is the shared engine behind 'nodes at distance K' and 'burn the tree'?

Both use a parent map and BFS. Distance K reads one layer; Burn counts the layers.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
69 / DRILL UNIT 17 · Burn the Tree · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Infection starts at a leaf. Its parent is the root, and the root has one other child, also a leaf. How many minutes until all three nodes are infected?

2. The start at minute 0, the root at 1, the other leaf at 2.

DRILL 02 · RECALL

LeetCode 2385 gives start as a value, not a node. What is the cheapest way to get the node the BFS begins from?

Pick it up in the pass that records parents. That pass already visits every node, so comparing each value with start costs nothing extra.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
70 / PROBLEM #21 · ANCESTORS · MED

Amount of Time for Binary Tree to Be Infected

MED ancestors ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Minutes until the whole tree is infected from one node.” Burn the Tree with a judge: the distance to the farthest node.

INTUITION

Infection spreads to the parent and both children, so treat the tree as a graph. The answer is the number of BFS layers.

STEPS
  1. one pass: record parent[node], and remember the node whose value is start
  2. BFS from that node: queue = {it}, seen = {it}, minutes = −1
  3. each round: minutes++, then pop the whole layer
  4. push left, right and parent of each popped node, unless seen
  5. when the queue is empty, return minutes
↕ SCROLL
// Parents turn the tree into a graph; the answer is the last BFS layer.
int amountOfTime(TreeNode* root, int start) {
    unordered_map<TreeNode*, TreeNode*> parent;
    TreeNode* src = nullptr;
    stack<TreeNode*> st; st.push(root); parent[root] = nullptr;
    while (!st.empty()) {                 // explicit stack: the tree can be a chain
        TreeNode* n = st.top(); st.pop();
        if (n->val == start) src = n;     // start arrives as a value
        if (n->left)  { parent[n->left]  = n; st.push(n->left); }
        if (n->right) { parent[n->right] = n; st.push(n->right); }
    }
    queue<TreeNode*> q; q.push(src);
    unordered_set<TreeNode*> seen{src};
    int minutes = -1;                     // the start's own layer costs nothing
    while (!q.empty()) {
        minutes++;
        for (int i = q.size(); i > 0; i--) {
            TreeNode* node = q.front(); q.pop();
            for (TreeNode* nb : {node->left, node->right, parent[node]})
                if (nb && !seen.count(nb)) { seen.insert(nb); q.push(nb); }
        }
    }
    return minutes;
}
TIMEO(n)one pass for parents, one BFS
SPACEO(n)parent map, seen set and queue
TRAP

Counting the start's own layer. The node that begins infected costs zero minutes, so the counter starts at −1.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
71 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH PATTERN, AND WHY

Twenty-four problems came down to a few shapes. Each card is the phrase in a statement that picks one.

“HEIGHT / DEPTH / DIAMETER / BALANCED / BEST PATH”

one postorder that RETURNS a value up the tree, a global tracks the best

BOTTOM-UP POSTORDER + GLOBALO(n)
“SAME / SYMMETRIC / MIRROR”

recurse on two nodes in lockstep, comparing structure and values

PAIRED RECURSIONO(n)
“BY LEVEL” / “ZIG-ZAG” / “RIGHT VIEW” / “WIDTH”

BFS with size-batches; one batch is one level, read left→right or reversed

LEVEL-BATCHED BFSO(n)
“VERTICAL / TOP / BOTTOM VIEW”

BFS carrying a horizontal column index; bucket nodes by column

BFS + COLUMN INDEXO(n log n)
“ROOT-TO-LEAF” / “PATH SUM” / “PRINT PATHS”

carry the path (or running sum) down; test or record it at a leaf

DFS CARRYING THE PATHO(n) · O(n²) to print
“NO LARGER VALUE ABOVE” / “NUMBER SPELLED BY THE PATH” / “ZIG-ZAG PATH”

pass the state DOWN as an argument; nothing to pop, each call has its own copy

DFS CARRYING A VALUE DOWNO(n)
“IS A SUBTREE OF” / “DUPLICATE SUBTREES”

compare from every node, or give each subtree an id built from its children's ids

SUBTREE AS A KEYO(n·m) → O(n)
“LCA” / “DISTANCE K” / “NEAREST”

LCA is one bottom-up pass; distance-K turns the tree into a graph + BFS

ANCESTOR / TREE-AS-GRAPHO(n)
“MINUTES TO INFECT / BURN” / “FARTHEST NODE FROM”

the same undirected graph; count BFS layers until the queue is empty

TREE-AS-GRAPH · LAYER COUNTO(n)
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
72 / RECALL RETRIEVAL, NOT RECOGNITION

NAME THE PATTERN FROM THE STATEMENT

DRILL 01 · TRANSFER

Diameter of a binary tree: why can't you just return the diameter recursively. Why does it need a global (or a returned pair)?

A node returns its height but records a diameter. The parent needs the height; the diameter goes into a global.

DRILL 02 · RECALL

Lowest Common Ancestor in a (non-BST) binary tree returns the node where the two targets split. What does the recursion return, and how does it detect the LCA?

Both sides non-null ⇒ this node is the split. A null, p or q returns itself; otherwise pass up the non-null side.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
73 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

Tree bugs pass the sample and fail the judge. Each one below gives a believable wrong number.

RETURNING THE DIAMETER INSTEAD OF THE HEIGHT

A node returns its height. The answer (diameter, path sum) lives in a global.

NAIVE DIAMETER: O(n²)

Computing height separately at every node to get its diameter re-walks subtrees repeatedly, O(n²).

MAX PATH SUM: NOT CLAMPING NEGATIVE GAINS TO 0

A child that contributes a negative sum should be dropped, not added. Take max(0, gain(child)).

SYMMETRIC: COMPARING left-left INSTEAD OF left-right

Compare left's LEFT with right's RIGHT, and left's right with right's left.

MAX WIDTH: INTEGER OVERFLOW ON THE INDEX

Indexing slots as 2i/2i+1 makes indices double each level and overflow for deep trees.

READING queue.size() INSIDE THE LEVEL LOOP

Snapshot the level size before the inner loop, or two levels merge.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
74 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Seventeen patterns, one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Max depth
O(n)
O(h)
1 + max(depth(left), depth(right))
Balanced
O(n)
O(h)
height helper returning −1 as an 'unbalanced' sentinel
Diameter
O(n)
O(h)
return height; global = max(global, leftH + rightH)
Max path sum
O(n)
O(h)
clamp L, R at 0; return val + max(L, R); global = val + L + R
Same / Symmetric / Invert
O(n)
O(h)
Same / Symmetric: paired recursion, mirror = left↔right. Invert: swap the children at every node
Level order / zig-zag / right view
O(n)
O(w)
BFS, batch by queue.size(), reverse/last per level
Vertical / top / bottom view
O(n log n)
O(n)
BFS carrying a column index; bucket by column
Max width
O(n)
O(w)
number slots 2i / 2i+1 per level; width = last − first + 1
Root-to-leaf paths / path sum
O(n)·O(n·h)
O(h)
carry path or running sum down; test at a leaf
Path sum III (any path)
O(n)
O(n)
prefix-sum count with a hashmap of prefix→count
LCA
O(n)
O(h)
both subtrees non-null ⇒ this node is the LCA
Nodes at distance K
O(n)
O(n)
parent map, then BFS K steps from the target
Time to infect / burn
O(n)
O(n)
same graph; count BFS layers, starting the counter at −1
Subtree of another tree
O(n·m)
O(h)
Same Tree launched from every node; nulls must match
Duplicate subtrees
O(n)
O(n)
id per (val, left id, right id); report when count hits 2
Good nodes / root-to-leaf number
O(n)
O(h)
carry max or cur·10+val DOWN as an argument
Longest zigzag
O(n)
O(h)
carry (viaLeft, viaRight) down; left child gets (viaRight+1, 0)
INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
75 / CLOSE STEP 13 · DECK 2 OF 3

READ THE SHAPE

Two shapes did most of the work: a postorder that returns a value while a global watches, and a level-batched BFS.

00%
OF THIS DECK SOLVED
← ALL TOPICS← DECK 1 · TRAVERSALSSTEP 07 · RECURSION

Deck 2 of 3. Top view, bottom view and boundary are concept units: LeetCode has no free judge for them.

INVARIANT · BINARY TREES · PROPERTIES, VIEWS & PATHS · DECK 2 OF 3
■ TOO SMALL TO READ
1280×720
INVARIANT · STEP 13 · DECK 2 OF 3

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.