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.
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.
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.
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.
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.
“Maximum depth / height of the tree.” The base case of the whole bottom-up family.
A node's depth is 1 plus the deeper of its two children. Recurse; an empty subtree is 0.
// 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)); }
// Height = 1 + the taller subtree; empty = 0. public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }
# Height = 1 + the taller subtree; empty = 0. def maxDepth(root): if root is None: return 0 return 1 + max(maxDepth(root.left), maxDepth(root.right))
Nodes or edges. LeetCode counts nodes: an empty tree is 0, one node is 1.
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.
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.
“Is the tree height-balanced?” (every node's subtrees differ in height by ≤ 1). A height recursion with an early-exit sentinel.
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.
// 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; }
// Height helper returns -1 as an 'unbalanced below' sentinel. int height(TreeNode node) { if (node == null) return 0; int l = height(node.left); if (l == -1) return -1; // bail out early int r = height(node.right); if (r == -1) return -1; if (Math.abs(l - r) > 1) return -1; // -1 can never be a real height return 1 + Math.max(l, r); } public boolean isBalanced(TreeNode root) { return height(root) != -1; // one postorder pass, O(n) }
# Height helper returns -1 as an 'unbalanced below' sentinel. def isBalanced(root): def height(node): if node is None: return 0 l = height(node.left) if l == -1: return -1 r = height(node.right) if r == -1: return -1 if abs(l - r) > 1: # unbalanced here return -1 return 1 + max(l, r) return height(root) != -1
Calling height() at every node: O(n²). Fold the check into one height pass that returns −1 once unbalanced.
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.
The longest path through a node is L + R, but it can only hand up 1 + max(L, R). Record one, return the other.
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.
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.
“Diameter, longest path between any two nodes.” The path need not pass the root, so track a global while returning heights.
Run the height recursion; at each node the longest bending path is leftH + rightH. Update a global max with it.
// 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; }
// Return height; update the global diameter with leftH + rightH. int best = 0; int height(TreeNode node) { if (node == null) return 0; int l = height(node.left); int r = height(node.right); best = Math.max(best, l + r); // longest path BENDING here return 1 + Math.max(l, r); // what the parent needs } public int diameterOfBinaryTree(TreeNode root) { height(root); return best; }
# Return height; update the global diameter with leftH + rightH. def diameterOfBinaryTree(root): best = 0 def height(node): nonlocal best if node is None: return 0 l = height(node.left) r = height(node.right) best = max(best, l + r) # longest path bending at node (edges) return 1 + max(l, r) # RETURN height, not diameter height(root) return best
Returning the diameter instead of the height. The parent needs the height; the diameter goes in a global.
Diameter with values. A negative branch is dropped: max(0, gain). Record val + L + R, return val + max(L, R).
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.
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).
“Maximum path sum, path may start and end anywhere.” Diameter with values, negatives allowed. Clamp and track a global.
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).
// 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; }
// Clamp child gains to 0; track val+L+R, return val+max(L,R). int best = Integer.MIN_VALUE; int gain(TreeNode node) { if (node == null) return 0; int l = Math.max(0, gain(node.left)); // drop a negative branch int r = Math.max(0, gain(node.right)); best = Math.max(best, node.val + l + r); // a path PEAKING here return node.val + Math.max(l, r); // upward: only one side } public int maxPathSum(TreeNode root) { gain(root); return best; }
# Clamp child gains to 0; track val+L+R, return val+max(L,R). def maxPathSum(root): best = float('-inf') def gain(node): nonlocal best if node is None: return 0 l = max(0, gain(node.left)) # drop a negative branch r = max(0, gain(node.right)) best = max(best, node.val + l + r) # best path bending here return node.val + max(l, r) # continue up via ONE child gain(root) return best
Not clamping negatives, or starting best at 0. Drop a negative child (use 0), and start best at −∞: every value may be negative.
Walk two trees together and compare the nodes at each position. Null against non-null is already a difference.
At every node of the big tree, run Same Tree against the pattern. It has to match all the way down to the nulls.
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.
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.
“Are two trees identical?” Structure and values must match, a paired recursion.
Both null: match. One null, or different values: mismatch. Otherwise compare left with left and right with right.
// 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); }
// Compare two trees in lockstep. public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; // both empty -> match if (p == null || q == null || p.val != q.val) return false; return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }
# Compare two trees in lockstep. def isSameTree(p, q): if not p and not q: # both empty -> match return True if not p or not q or p.val != q.val: return False return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
Mishandling the null cases. 'Both null' is a match (you reached the end together); 'exactly one null' is a mismatch (shapes differ).
“Is this tree a subtree of that one?” Same Tree, launched from every node.
Walk the big tree. At each node, run Same Tree against the pattern.
// 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); }
// Try every node of root as the anchor of a Same Tree match. public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) return false; // nowhere left to anchor if (same(root, subRoot)) return true; return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); } private boolean same(TreeNode a, TreeNode b) { if (a == null || b == null) return a == b; // null against a node: different return a.val == b.val && same(a.left, b.left) && same(a.right, b.right); }
# Try every node of root as the anchor of a Same Tree match. def isSubtree(root, subRoot): def same(a, b): if not a or not b: return a is b # null against a node: different return (a.val == b.val and same(a.left, b.left) and same(a.right, b.right)) if not root: return False # nowhere left to anchor if same(root, subRoot): return True return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)
Stopping when the pattern runs out. Extra descendants in the big tree must make the match fail.
“Return every subtree that appears more than once.” Give each subtree a key, and count the keys.
Give each distinct subtree an id. Its key is (value, left id, right id). A key seen twice is a duplicate.
// 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; }
// Give every distinct subtree an id; a subtree is (value, left id, right id). Map<String, Integer> ids = new HashMap<>(); Map<Integer, Integer> seen = new HashMap<>(); List<TreeNode> res = new ArrayList<>(); public List<TreeNode> findDuplicateSubtrees(TreeNode root) { dfs(root); return res; } private int dfs(TreeNode node) { if (node == null) return 0; // every empty subtree is id 0 String key = node.val + "," + dfs(node.left) + "," + dfs(node.right); if (!ids.containsKey(key)) ids.put(key, ids.size() + 1); int id = ids.get(key); if (seen.merge(id, 1, Integer::sum) == 2) res.add(node); // second sighting only return id; }
# Give every distinct subtree an id; a subtree is (value, left id, right id). def findDuplicateSubtrees(root): ids, seen, res = {}, {}, [] def dfs(node): if not node: return 0 # every empty subtree is id 0 key = (node.val, dfs(node.left), dfs(node.right)) if key not in ids: ids[key] = len(ids) + 1 uid = ids[key] seen[uid] = seen.get(uid, 0) + 1 if seen[uid] == 2: # the second sighting only res.append(node) return uid dfs(root) return res
Writing the whole subtree out as the key. Correct, but a chain builds O(n²) characters.
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.
Two pointers into one tree, paired outside with outside: (a.left, b.right) and (a.right, b.left).
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.
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.
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.
“Is the tree a mirror of itself?” Compare the two halves with a MIRRORED paired recursion.
Symmetry means the left subtree mirrors the right. Compare left.left with right.right and left.right with right.left, the cross-pairing.
// 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); }
// Mirror check: cross-pair the children. boolean isMirror(TreeNode a, TreeNode b) { if (a == null && b == null) return true; if (a == null || b == null || a.val != b.val) return false; return isMirror(a.left, b.right) // OUTER pair && isMirror(a.right, b.left); // INNER pair } public boolean isSymmetric(TreeNode root) { return root == null || isMirror(root.left, root.right); }
# Mirror check: cross-pair the children. def isSymmetric(root): def isMirror(a, b): if not a and not b: return True if not a or not b or a.val != b.val: return False return isMirror(a.left, b.right) and isMirror(a.right, b.left) return not root or isMirror(root.left, root.right)
Comparing same-side children (left.left with right.left). That checks whether the two subtrees are identical, not mirror images.
“Invert / mirror the tree.” Swap every node's two children.
Swap each node's left and right, then recurse into both. The result is the mirror Symmetric tests for.
// 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; }
// Swap children at every node. public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode t = root.left; root.left = root.right; root.right = t; invertTree(root.left); invertTree(root.right); return root; }
# Swap children at every node. def invertTree(root): if root is None: return None root.left, root.right = root.right, root.left invertTree(root.left) invertTree(root.right) return root
Swapping AFTER recursing without care, or forgetting to return the root. Swap then recurse, or recurse then swap.
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.
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.
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.
“Zig-zag / spiral level order.” Level order with the direction flipped each level.
Size-batched BFS plus a direction flag. On a right-to-left level, fill the level list from the back.
// 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; }
// Level order; reverse the placement on alternate levels. public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new ArrayDeque<>(); q.add(root); boolean leftToRight = true; while (!q.isEmpty()) { int n = q.size(); // exactly this level Integer[] level = new Integer[n]; for (int i = 0; i < n; i++) { TreeNode node = q.poll(); level[leftToRight ? i : n - 1 - i] = node.val; // place, do not push if (node.left != null) q.add(node.left); // ALWAYS left first if (node.right != null) q.add(node.right); } res.add(Arrays.asList(level)); leftToRight = !leftToRight; } return res; }
# Level order; reverse the placement on alternate levels. from collections import deque def zigzagLevelOrder(root): res = [] if not root: return res q = deque([root]) left_to_right = True while q: n = len(q) level = [0] * n for i in range(n): node = q.popleft() idx = i if left_to_right else n - 1 - i # place, don't reorder queue level[idx] = node.val if node.left: q.append(node.left) if node.right: q.append(node.right) left_to_right = not left_to_right res.append(level) return res
Flipping the push order. Always enqueue left, then right. Flip only the output.
Level order again. Each node is keyed by its level and the last one per level wins. First wins would give the left view.
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.
“Right side view, the rightmost node of each level.” Size-batched BFS, take the last.
BFS by level; the last node popped in each level is its rightmost. Record it.
// 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; }
// The last node popped in each BFS level is the rightmost. public List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new ArrayDeque<>(); q.add(root); while (!q.isEmpty()) { int n = q.size(); for (int i = 0; i < n; i++) { TreeNode node = q.poll(); if (i == n - 1) res.add(node.val); // the LAST of this level if (node.left != null) q.add(node.left); if (node.right != null) q.add(node.right); } } return res; }
# The last node popped in each BFS level is the rightmost. from collections import deque def rightSideView(root): res = [] if not root: return res q = deque([root]) while q: n = len(q) for i in range(n): node = q.popleft() if i == n - 1: # rightmost of level res.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return res
Following right pointers only. A node from the left subtree can be rightmost on a deep level.
Every node has an extra pointer, next, null at first. Point it at the node to its right on the same level.
In a perfect tree: left.next = right, and right.next = node.next ? node.next.left : null. The level above's links do the work.
// 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; }
// Perfect tree: wire level L+1 using level L's next chain. O(1) space. public Node connect(Node root) { Node leftmost = root; while (leftmost != null && leftmost.left != null) { Node node = leftmost; while (node != null) { node.left.next = node.right; // within this parent if (node.next != null) node.right.next = node.next.left; // across to the neighbour node = node.next; // walk level L via next } leftmost = leftmost.left; // drop to level L+1 } return root; }
# Perfect tree: wire level L+1 using level L's next chain. O(1) space. def connect(root): leftmost = root while leftmost and leftmost.left: node = leftmost while node: node.left.next = node.right node.right.next = node.next.left if node.next else None node = node.next # walk the current level leftmost = leftmost.left # drop to the next level return root
Using a queue when O(1) space is expected. Wire each level from the next links of the level above.
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.
Key each node by column: root 0, left −1, right +1. Keep the first node per column. BFS makes first mean highest.
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.
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.
Top view with the guard removed: overwrite every time, so the last, deepest node per column stays.
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.
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.
Keep every node, grouped by column. Nodes in the same row and column are ordered by value.
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).
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.
“Vertical order traversal.” Group nodes by column; within a column order by (row, value).
BFS with (row, col): left child col − 1, right child col + 1. Bucket by column, then sort each column by (row, value).
// 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; }
// BFS carrying (row, col); bucket by column, sort by (row, val). public List<List<Integer>> verticalTraversal(TreeNode root) { // TreeMap keeps the columns in left-to-right order for free TreeMap<Integer, List<int[]>> cols = new TreeMap<>(); Queue<Object[]> q = new ArrayDeque<>(); if (root != null) q.add(new Object[]{root, 0, 0}); while (!q.isEmpty()) { Object[] cur = q.poll(); TreeNode node = (TreeNode) cur[0]; int row = (int) cur[1], col = (int) cur[2]; cols.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val}); if (node.left != null) q.add(new Object[]{node.left, row + 1, col - 1}); if (node.right != null) q.add(new Object[]{node.right, row + 1, col + 1}); } List<List<Integer>> res = new ArrayList<>(); for (List<int[]> bucket : cols.values()) { // same column: by row, then by VALUE - that tie-break is the spec bucket.sort((x, y) -> x[0] != y[0] ? x[0] - y[0] : x[1] - y[1]); List<Integer> out = new ArrayList<>(); for (int[] e : bucket) out.add(e[1]); res.add(out); } return res; }
# BFS carrying (row, col); bucket by column, sort by (row, val). from collections import deque, defaultdict def verticalTraversal(root): cols = defaultdict(list) # col -> list of (row, val) q = deque([(root, 0, 0)]) while q: node, row, col = q.popleft() cols[col].append((row, node.val)) if node.left: q.append((node.left, row + 1, col - 1)) if node.right: q.append((node.right, row + 1, col + 1)) res = [] for col in sorted(cols): res.append([val for row, val in sorted(cols[col])]) # by row, then value return res
Missing the tie-break. Two nodes in the same column and row are ordered by value.
Three passes: left edge down, leaves left to right, right edge up. Keep leaves out of the edge passes, or they print twice.
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.
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.
Number each level's slots, gaps included: the children of i are 2i and 2i+1. Width = last − first + 1.
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.
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.
“Maximum width, counting null gaps.” Number the slots; width = last − first + 1.
BFS carrying a slot number (children in slots 2i, 2i+1). Per level, width is the last slot minus the first plus 1.
// 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; }
// Slot numbers; normalise per level to avoid overflow. public int widthOfBinaryTree(TreeNode root) { if (root == null) return 0; int best = 0; Queue<Object[]> q = new ArrayDeque<>(); q.add(new Object[]{root, 0L}); // a Long: the casts below unbox it while (!q.isEmpty()) { int n = q.size(); int first = 0, last = 0; long base = (long) q.peek()[1]; // re-base: indices double per level for (int i = 0; i < n; i++) { Object[] cur = q.poll(); TreeNode node = (TreeNode) cur[0]; int idx = (int) ((long) cur[1] - base); if (i == 0) first = idx; if (i == n - 1) last = idx; if (node.left != null) q.add(new Object[]{node.left, 2L * idx}); if (node.right != null) q.add(new Object[]{node.right, 2L * idx + 1}); } best = Math.max(best, last - first + 1); // counts the null GAPS too } return best; }
# Slot numbers; normalise per level to avoid overflow. from collections import deque def widthOfBinaryTree(root): if not root: return 0 best = 0 q = deque([(root, 0)]) while q: n = len(q) first = q[0][1] last = first for _ in range(n): node, idx = q.popleft() idx -= first # re-base to avoid overflow last = idx if node.left: q.append((node.left, 2 * idx)) if node.right: q.append((node.right, 2 * idx + 1)) best = max(best, last + 1) return best
Index overflow. 2i+1 doubles every level. Subtract the level's first index as you go.
Carry the path down and print it at each leaf. Pop on the way out, or it leaks into the sibling branch.
Here information flows down: each call gets mx, the largest value above it. A node is good when val ≥ mx.
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.
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.
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.
“Print all root-to-leaf paths.” Carry the path down; record it at each leaf.
DFS carrying the path so far. At a leaf, record the completed path.
// 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; }
// Carry the path down; emit it at each leaf. void dfs(TreeNode node, String path, List<String> res) { if (node == null) return; path += node.val; if (node.left == null && node.right == null) { res.add(path); return; } path += "->"; dfs(node.left, path, res); // String is immutable, so each dfs(node.right, path, res); // branch gets its own copy free }
# Carry the path down; emit it at each leaf. def binaryTreePaths(root): res = [] def dfs(node, path): if not node: return path = path + str(node.val) if not node.left and not node.right: res.append(path); return path += "->" dfs(node.left, path) dfs(node.right, path) dfs(root, "") return res
Recording at a null or a one-child node. A path ends only at a leaf.
“Does a root-to-leaf path sum to the target?” Subtract on the way down; test at a leaf.
Recurse subtracting the node's value from the remaining target. At a leaf, success is remaining == node value.
// 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); }
// Root-to-leaf sum == target: subtract down, check at leaves. public boolean hasPathSum(TreeNode node, int target) { if (node == null) return false; if (node.left == null && node.right == null) return target == node.val; return hasPathSum(node.left, target - node.val) || hasPathSum(node.right, target - node.val); }
# Root-to-leaf sum == target: subtract down, check at leaves. def hasPathSum(node, target): if not node: return False if not node.left and not node.right: return target == node.val return (hasPathSum(node.left, target - node.val) or hasPathSum(node.right, target - node.val))
Returning true at null. An empty child is not a finished path. Test only at a real leaf.
“Collect all root-to-leaf paths summing to the target.” DFS with backtracking.
Carry the current path and remaining target. At a leaf that hits 0, record a copy of the path.
// 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; }
// Backtracking: push, recurse, pop; record a copy at a matching leaf. void dfs(TreeNode node, int target, List<Integer> path, List<List<Integer>> res) { if (node == null) return; path.add(node.val); target -= node.val; if (node.left == null && node.right == null && target == 0) res.add(new ArrayList<>(path)); // a COPY: path keeps mutating dfs(node.left, target, path, res); dfs(node.right, target, path, res); path.remove(path.size() - 1); // undo before the sibling }
# Backtracking: push, recurse, pop; record a copy at a matching leaf. def pathSum(root, target): res, path = [], [] def dfs(node, target): if not node: return path.append(node.val) target -= node.val if not node.left and not node.right and target == 0: res.append(path[:]) # a COPY of the current path else: dfs(node.left, target) dfs(node.right, target) path.pop() # backtrack dfs(root, target) return res
Not popping, or saving the shared path. Pop on the way out, and save a copy (Python path[:]).
“Each root-to-leaf path spells a number; add them all.” Carry the number down, return it at a leaf.
Each step down appends a digit: cur = cur * 10 + val. Return cur at a leaf; every other node returns its children's sum.
// 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); }
// Carry the number built so far down; a leaf returns it. public int sumNumbers(TreeNode root) { return dfs(root, 0); } private int dfs(TreeNode node, int cur) { if (node == null) return 0; // a missing child adds nothing cur = cur * 10 + node.val; // one level down appends a digit if (node.left == null && node.right == null) return cur; return dfs(node.left, cur) + dfs(node.right, cur); }
# Carry the number built so far down; a leaf returns it. def sumNumbers(root): def dfs(node, cur): if not node: return 0 # a missing child adds nothing cur = cur * 10 + node.val # one level down appends a digit if not node.left and not node.right: return cur return dfs(node.left, cur) + dfs(node.right, cur) return dfs(root, 0)
Returning cur at a null child. A one-child node would count a half-built number.
“Count nodes with no larger value on the path from the root.” State carried down, not returned up.
Whether a node is good depends on what lies above it. Pass the largest value so far down as an argument.
// 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 }
// Carry the largest value on the path down as an argument. public int goodNodes(TreeNode root) { return dfs(root, Integer.MIN_VALUE); // the root is always good } private int dfs(TreeNode node, int mx) { if (node == null) return 0; int good = node.val >= mx ? 1 : 0; // nothing above is bigger mx = Math.max(mx, node.val); // the cap for everything below return good + dfs(node.left, mx) + dfs(node.right, mx); }
# Carry the largest value on the path down, one stack entry per node. def goodNodes(root): count, stack = 0, [(root, float('-inf'))] while stack: # explicit stack: 1e5 nodes can be a chain node, mx = stack.pop() if node.val >= mx: # nothing above is bigger count += 1 mx = max(mx, node.val) # the cap for everything below if node.left: stack.append((node.left, mx)) if node.right: stack.append((node.right, mx)) return count
Comparing with the parent only. A grandparent can still be larger.
“Longest path that alternates left and right.” Carry two lengths down: arrived by a left step, arrived by a right step.
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.
// 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; }
// Carry down the zigzag length ending at each node, by last step. int best = 0; public int longestZigZag(TreeNode root) { best = 0; dfs(root, 0, 0); return best; } private void dfs(TreeNode node, int viaLeft, int viaRight) { if (node == null) return; best = Math.max(best, Math.max(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 }
# Carry down the zigzag length ending at each node, by last step. def longestZigZag(root): best = 0 stack = [(root, 0, 0)] # explicit stack: 5e4 nodes can be a chain while stack: node, viaLeft, viaRight = stack.pop() best = max(best, viaLeft, viaRight) if node.left: # step left: extends a path that arrived by a right step stack.append((node.left, viaRight + 1, 0)) if node.right: # step right: extends a path that arrived by a left step stack.append((node.right, 0, viaLeft + 1)) return best
Extending with the same direction. Two lefts in a row restart the count at 1.
“Count paths (any node down to any descendant) summing to target.” Prefix-sum + hashmap.
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.
// 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; }
// Prefix-sum count: paths ending here with sum target. int total = 0; void dfs(TreeNode node, long running, long target, Map<Long,Integer> seen) { if (node == null) return; running += node.val; total += seen.getOrDefault(running - target, 0); // starts that qualify seen.merge(running, 1, Integer::sum); dfs(node.left, running, target, seen); dfs(node.right, running, target, seen); seen.merge(running, -1, Integer::sum); // leave the path as you found it } public int pathSum(TreeNode root, int target) { Map<Long,Integer> seen = new HashMap<>(); seen.put(0L, 1); // the empty prefix dfs(root, 0, target, seen); return total; }
# Prefix-sum count: paths ending here with sum target. from collections import defaultdict def pathSum(root, target): seen = defaultdict(int); seen[0] = 1 total = 0 def dfs(node, running): nonlocal total if not node: return running += node.val total += seen[running - target] seen[running] += 1 dfs(node.left, running) dfs(node.right, running) seen[running] -= 1 # backtrack the map dfs(root, 0) return total
Not undoing the prefix count. Decrement it after a node's subtrees, or one branch's sums leak into its sibling.
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.
Each call returns what it found. A node that hears from both sides is the LCA; every other node just passes the answer up.
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.
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.
“Lowest common ancestor in a binary tree” (not a BST). One bottom-up pass.
Null, p or q: return the node. If both sides return something, this node is the LCA. Otherwise pass up the side that did.
// 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) }
// Both subtrees report a target -> this node is the LCA. public TreeNode lowestCommonAncestor(TreeNode node, TreeNode p, TreeNode q) { if (node == null || node == p || node == q) return node; TreeNode left = lowestCommonAncestor(node.left, p, q); TreeNode right = lowestCommonAncestor(node.right, p, q); if (left != null && right != null) return node; // one each side return (left != null) ? left : right; // propagate the finding }
# Both subtrees report a target -> this node is the LCA. def lowestCommonAncestor(node, p, q): if not node or node == p or node == q: return node left = lowestCommonAncestor(node.left, p, q) right = lowestCommonAncestor(node.right, p, q) if left and right: # p and q on different sides return node return left if left else right
Steering by value. That only works in a BST. A plain tree is unordered, so search both sides.
Distance K has to go up as well. Record each node's parent, then BFS from the target and stop at layer K.
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.
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.
“All nodes at distance K from a target.” Turn the tree into a graph, then BFS.
Distance-K nodes can be above the target. Build a parent map, then BFS from the target over left, right and parent, K layers.
// 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; }
// Parent map turns the tree into a graph; BFS K layers from target. public List<Integer> distanceK(TreeNode root, TreeNode target, int K) { Map<TreeNode, TreeNode> parent = new HashMap<>(); mark(root, null, parent); Queue<TreeNode> q = new ArrayDeque<>(); Set<TreeNode> seen = new HashSet<>(); // the graph is UNDIRECTED now q.add(target); seen.add(target); int dist = 0; while (!q.isEmpty()) { if (dist == K) { List<Integer> res = new ArrayList<>(); for (TreeNode n : q) res.add(n.val); return res; } int n = q.size(); for (int i = 0; i < n; i++) { TreeNode cur = q.poll(); for (TreeNode nx : new TreeNode[]{cur.left, cur.right, parent.get(cur)}) if (nx != null && seen.add(nx)) q.add(nx); // add() reports new } dist++; } return new ArrayList<>(); } private void mark(TreeNode n, TreeNode p, Map<TreeNode, TreeNode> parent) { if (n == null) return; parent.put(n, p); mark(n.left, n, parent); mark(n.right, n, parent); }
# Parent map turns the tree into a graph; BFS K layers from target. from collections import deque def distanceK(root, target, K): parent = {} def mark(n, p): if not n: return parent[n] = p; mark(n.left, n); mark(n.right, n) mark(root, None) q = deque([target]); seen = {target}; dist = 0 while q: if dist == K: return [node.val for node in q] for _ in range(len(q)): node = q.popleft() for nb in (node.left, node.right, parent[node]): if nb and nb not in seen: seen.add(nb); q.append(nb) dist += 1 return []
Searching only downward, or no visited set. Go up through the parent map, and mark visited so you never loop.
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.
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.
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.
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.
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.
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.
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.
“Minutes until the whole tree is infected from one node.” Burn the Tree with a judge: the distance to the farthest node.
Infection spreads to the parent and both children, so treat the tree as a graph. The answer is the number of BFS layers.
// 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; }
// Parents turn the tree into a graph; the answer is the last BFS layer. public int amountOfTime(TreeNode root, int start) { Map<TreeNode, TreeNode> parent = new HashMap<>(); TreeNode src = null; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); parent.put(root, null); while (!stack.isEmpty()) { // explicit stack: no deep recursion TreeNode n = stack.pop(); if (n.val == start) src = n; // start arrives as a value if (n.left != null) { parent.put(n.left, n); stack.push(n.left); } if (n.right != null) { parent.put(n.right, n); stack.push(n.right); } } Queue<TreeNode> q = new ArrayDeque<>(); Set<TreeNode> seen = new HashSet<>(); q.add(src); seen.add(src); int minutes = -1; // the start's own layer costs nothing while (!q.isEmpty()) { minutes++; for (int i = q.size(); i > 0; i--) { TreeNode cur = q.poll(); for (TreeNode nb : new TreeNode[]{cur.left, cur.right, parent.get(cur)}) if (nb != null && seen.add(nb)) q.add(nb); // add() reports new } } return minutes; }
# Parents turn the tree into a graph; the answer is the last BFS layer. from collections import deque def amountOfTime(root, start): parent, src = {root: None}, None stack = [root] while stack: # explicit stack: the tree can be a chain node = stack.pop() if node.val == start: src = node # start arrives as a value for child in (node.left, node.right): if child: parent[child] = node stack.append(child) q, seen, minutes = deque([src]), {src}, -1 while q: minutes += 1 # the start's own layer costs nothing for _ in range(len(q)): node = q.popleft() for nb in (node.left, node.right, parent[node]): if nb and nb not in seen: seen.add(nb); q.append(nb) return minutes
Counting the start's own layer. The node that begins infected costs zero minutes, so the counter starts at −1.
Twenty-four problems came down to a few shapes. Each card is the phrase in a statement that picks one.
one postorder that RETURNS a value up the tree, a global tracks the best
BOTTOM-UP POSTORDER + GLOBALO(n)recurse on two nodes in lockstep, comparing structure and values
PAIRED RECURSIONO(n)BFS with size-batches; one batch is one level, read left→right or reversed
LEVEL-BATCHED BFSO(n)BFS carrying a horizontal column index; bucket nodes by column
BFS + COLUMN INDEXO(n log n)carry the path (or running sum) down; test or record it at a leaf
DFS CARRYING THE PATHO(n) · O(n²) to printpass the state DOWN as an argument; nothing to pop, each call has its own copy
DFS CARRYING A VALUE DOWNO(n)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 is one bottom-up pass; distance-K turns the tree into a graph + BFS
ANCESTOR / TREE-AS-GRAPHO(n)the same undirected graph; count BFS layers until the queue is empty
TREE-AS-GRAPH · LAYER COUNTO(n)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.
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.
Tree bugs pass the sample and fail the judge. Each one below gives a believable wrong number.
A node returns its height. The answer (diameter, path sum) lives in a global.
Computing height separately at every node to get its diameter re-walks subtrees repeatedly, O(n²).
A child that contributes a negative sum should be dropped, not added. Take max(0, gain(child)).
Compare left's LEFT with right's RIGHT, and left's right with right's left.
Indexing slots as 2i/2i+1 makes indices double each level and overflow for deep trees.
Snapshot the level size before the inner loop, or two levels merge.
Seventeen patterns, one page. The right column is the cue for each.
Two shapes did most of the work: a postorder that returns a value while a global watches, and a level-batched BFS.
Deck 2 of 3. Top view, bottom view and boundary are concept units: LeetCode has no free judge for them.
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.