The finale: count a complete tree fast, rebuild and serialize trees, walk with Morris in O(1) space, and finish on tree DP.
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.
Walk only left and only right from a node. Equal: the subtree is perfect, size 2h − 1. Not equal: 1 + left + right, and one side is always perfect.
Why does equal left-height and right-height mean the subtree is perfect?
Equal left and right depth means the last level is full. So the subtree is perfect.
Where does the O(log²n) come from?
O(log n) levels × O(log n) height walk. Each perfect subtree is answered by formula.
“Count nodes of a COMPLETE binary tree, better than O(n).” 'Complete' is the signal to exploit the shape.
Walk only left and only right. Equal heights mean the subtree is perfect: return 2^h − 1. Otherwise 1 + count(left) + count(right).
// Perfect subtrees counted by formula; recurse only the ragged path. int leftH(TreeNode* n) { int h = 0; while (n) { h++; n = n->left; } return h; } int rightH(TreeNode* n) { int h = 0; while (n) { h++; n = n->right; } return h; } int countNodes(TreeNode* root) { if (!root) return 0; int lh = leftH(root), rh = rightH(root); if (lh == rh) return (1 << lh) - 1; // perfect: 2^lh - 1 (1 << lh is 2^lh) return 1 + countNodes(root->left) + countNodes(root->right); }
// Perfect subtrees counted by formula; recurse only the ragged path. int leftH(TreeNode n) { int h = 0; while (n != null) { h++; n = n.left; } return h; } int rightH(TreeNode n) { int h = 0; while (n != null) { h++; n = n.right; } return h; } public int countNodes(TreeNode root) { if (root == null) return 0; int lh = leftH(root), rh = rightH(root); if (lh == rh) return (1 << lh) - 1; // perfect: 2^lh - 1 (1 << lh is 2^lh) return 1 + countNodes(root.left) + countNodes(root.right); }
# Perfect subtrees counted by formula; recurse only the ragged path. def countNodes(root): def leftH(n): h = 0 while n: h, n = h + 1, n.left return h def rightH(n): h = 0 while n: h, n = h + 1, n.right return h if not root: return 0 lh, rh = leftH(root), rightH(root) if lh == rh: return (1 << lh) - 1 # perfect: 2^lh - 1 return 1 + countNodes(root.left) + countNodes(root.right)
Counting every node, O(n). Use the equal-heights shortcut, so only one ragged path recurses: O(log²n).
Preorder names the roots; inorder says where each one splits. Take the next preorder value, find it in inorder: left of it is the left subtree, right of it the right.
What role does each of the two traversals play in the reconstruction?
Preorder gives the root; inorder gives the split.
Why build a hashmap of inorder values to indices instead of scanning inorder each time?
An O(1) root lookup keeps the build O(n). Scanning for the split each time is O(n) per node.
“Reconstruct the tree from preorder + inorder.” Two sequences, one unique tree.
Preorder's front is the root. Find it in inorder (with a value→index map) to split left from right, then recurse.
// Preorder gives roots; inorder (via a map) splits each subtree. unordered_map<int,int> pos; int preIdx = 0; TreeNode* build(vector<int>& pre, int inL, int inR) { if (inL > inR) return nullptr; int rootVal = pre[preIdx++]; // next root, preorder front-to-back TreeNode* root = new TreeNode(rootVal); int mid = pos[rootVal]; // its split point in inorder root->left = build(pre, inL, mid - 1); root->right = build(pre, mid + 1, inR); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i; preIdx = 0; return build(preorder, 0, inorder.size() - 1); }
// Preorder gives roots; inorder (via a map) splits each subtree. Map<Integer,Integer> pos = new HashMap<>(); int preIdx = 0; TreeNode build(int[] pre, int inL, int inR) { if (inL > inR) return null; int rootVal = pre[preIdx++]; // next root, preorder front-to-back TreeNode root = new TreeNode(rootVal); int mid = pos.get(rootVal); // its split point in inorder root.left = build(pre, inL, mid - 1); root.right = build(pre, mid + 1, inR); return root; } public TreeNode buildTree(int[] pre, int[] in) { for (int i = 0; i < in.length; i++) pos.put(in[i], i); return build(pre, 0, in.length - 1); }
# Preorder gives roots; inorder (via a map) splits each subtree. def buildTree(preorder, inorder): pos = {v: i for i, v in enumerate(inorder)} preIdx = 0 def build(inL, inR): nonlocal preIdx if inL > inR: return None rootVal = preorder[preIdx]; preIdx += 1 # next root, front-to-back root = TreeNode(rootVal) mid = pos[rootVal] # split point in inorder root.left = build(inL, mid - 1) root.right = build(mid + 1, inR) return root return build(0, len(inorder) - 1)
Scanning inorder for the root every call: O(n²). Precompute a value→index map, and build left before right.
Postorder's last value is the root. Read it backwards: take roots from the back and build the right side first.
Why must you build the right subtree before the left when using postorder from the back?
Postorder backwards is root-right-left. So the right subtree's roots come next: build right first.
What is common to both construction problems?
Inorder splits, the map keeps it O(n). That is the same whichever order you pair it with.
“Reconstruct the tree from inorder + postorder.” Same idea, postorder from the back.
Postorder's last value is the root. Read it from the back: roots come root-right-left, so build the RIGHT subtree first.
// Postorder (from the back) gives roots; build RIGHT before left. unordered_map<int,int> pos; int postIdx; TreeNode* build(vector<int>& post, int inL, int inR) { if (inL > inR) return nullptr; int rootVal = post[postIdx--]; // roots come out root-right-left TreeNode* root = new TreeNode(rootVal); int mid = pos[rootVal]; root->right = build(post, mid + 1, inR); // RIGHT first root->left = build(post, inL, mid - 1); return root; } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { for (int i = 0; i < inorder.size(); i++) pos[inorder[i]] = i; postIdx = postorder.size() - 1; return build(postorder, 0, inorder.size() - 1); }
// Postorder (from the back) gives roots; build RIGHT before left. Map<Integer,Integer> pos = new HashMap<>(); int postIdx; TreeNode build(int[] post, int inL, int inR) { if (inL > inR) return null; int rootVal = post[postIdx--]; // roots come out root-right-left TreeNode root = new TreeNode(rootVal); int mid = pos.get(rootVal); root.right = build(post, mid + 1, inR); // RIGHT first root.left = build(post, inL, mid - 1); return root; } public TreeNode buildTree(int[] in, int[] post) { for (int i = 0; i < in.length; i++) pos.put(in[i], i); postIdx = post.length - 1; return build(post, 0, in.length - 1); }
# Postorder (from the back) gives roots; build RIGHT before left. def buildTree(inorder, postorder): pos = {v: i for i, v in enumerate(inorder)} postIdx = len(postorder) - 1 def build(inL, inR): nonlocal postIdx if inL > inR: return None rootVal = postorder[postIdx]; postIdx -= 1 # root-right-left order root = TreeNode(rootVal) mid = pos[rootVal] root.right = build(mid + 1, inR) # RIGHT first root.left = build(inL, mid - 1) return root return build(0, len(inorder) - 1)
Building left before right. From the back, the next roots belong to the right subtree.
Values alone can't be read back. Write preorder with a # for every missing child; those markers are the shape.
Read the tokens front to back. A number makes a node and builds its left, then its right; a # is an empty child.
Why are null markers essential in the serialized string?
Markers fix the shape. The values 1,2,3 alone fit many trees.
How does deserialize know when to stop building a subtree?
The token order is the shape. A value opens a node; a # ends a branch.
“Serialize a tree to a string and deserialize it back.” Encode with null markers.
Write preorder with a '#' for every null. Read the tokens in the same order: a value makes a node and reads two children; '#' is null.
// Preorder with '#' null markers; deserialize consumes tokens in order. void write(TreeNode* n, string& s) { if (!n) { s += "#,"; return; } s += to_string(n->val) + ","; write(n->left, s); write(n->right, s); } string serialize(TreeNode* root) { string s; write(root, s); return s; } TreeNode* read(string& data, int& i) { // i = start of the next token int j = data.find(',', i); string tok = data.substr(i, j - i); i = j + 1; if (tok == "#") return nullptr; TreeNode* n = new TreeNode(stoi(tok)); n->left = read(data, i); n->right = read(data, i); return n; } TreeNode* deserialize(string data) { int i = 0; return read(data, i); }
// Preorder with '#' null markers; deserialize consumes tokens in order. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); dfs(root, sb); return sb.toString(); } private void dfs(TreeNode n, StringBuilder sb) { if (n == null) { sb.append("#,"); return; } sb.append(n.val).append(','); dfs(n.left, sb); dfs(n.right, sb); } private int idx; public TreeNode deserialize(String data) { idx = 0; return build(data.split(",")); } private TreeNode build(String[] t) { String tok = t[idx++]; if (tok.equals("#")) return null; // marker ends this branch TreeNode node = new TreeNode(Integer.parseInt(tok)); node.left = build(t); // stream order encodes the shape node.right = build(t); return node; }
# Preorder with '#' null markers; deserialize consumes tokens in order. class Codec: def serialize(self, root): out = [] def dfs(n): if not n: out.append('#'); return out.append(str(n.val)) dfs(n.left); dfs(n.right) dfs(root) return ','.join(out) def deserialize(self, data): it = iter(data.split(',')) def build(): tok = next(it) if tok == '#': return None n = TreeNode(int(tok)) n.left = build(); n.right = build() return n return build()
No null markers. Without a '#' for every missing child, many trees give the same string.
Go left once, then right to the end: that node's null right pointer is pointed back at us, a thread. Meeting the thread again means the left side is done: remove it, record, go right.
What does Morris traversal use instead of a stack to get back up the tree?
A borrowed right pointer. The predecessor's null right pointer is aimed back at the node, so the walk can climb up with no stack.
Why must the thread be removed on the second visit?
A leftover thread is a cycle. On the second visit, remove it, record the node, go right.
Recurse right, then left, then link the node in front of the finished tail in prev. Nothing is overwritten before it is used.
At each node with a left subtree, hang the right subtree on the left's rightmost node, move left to the right, clear left. O(n) time, O(1) space.
In the O(1) flatten, why attach the current node's right subtree to the rightmost node of its left subtree?
The right subtree comes after the whole left subtree. So it hangs off the left subtree's rightmost node.
What makes this flatten O(1) space rather than O(n) (e.g. collecting preorder into a list)?
It reuses the tree's own pointers. No list, no stack: O(1) extra space.
“Flatten the tree to a right-skewed linked list, preorder order, in place.” O(1) space via a Morris-like rewire.
For each node with a left subtree: hang its right subtree on the left subtree's rightmost node, move left to the right, clear left, step right.
// In-place: splice the right subtree onto the left subtree's tail. void flatten(TreeNode* root) { TreeNode* cur = root; while (cur) { if (cur->left) { TreeNode* rightmost = cur->left; while (rightmost->right) rightmost = rightmost->right; // rightmost of left subtree rightmost->right = cur->right; // old right hangs off it cur->right = cur->left; // left subtree becomes right cur->left = nullptr; } cur = cur->right; // advance down the list } }
// In-place: splice the right subtree onto the left subtree's tail. public void flatten(TreeNode root) { TreeNode cur = root; while (cur != null) { if (cur.left != null) { TreeNode rightmost = cur.left; while (rightmost.right != null) rightmost = rightmost.right; // rightmost of left rightmost.right = cur.right; // old right hangs off it cur.right = cur.left; // left subtree becomes right cur.left = null; } cur = cur.right; // walk the growing list } }
# In-place: splice the right subtree onto the left subtree's tail. def flatten(root): cur = root while cur: if cur.left: rightmost = cur.left while rightmost.right: # rightmost of left subtree rightmost = rightmost.right rightmost.right = cur.right # old right hangs off it cur.right = cur.left # left subtree becomes right cur.left = None cur = cur.right # advance down the list
Collecting preorder into a list first: O(n) space. Rewire in place, and remember to clear the left pointer.
No two robbed houses may share an edge. Each node returns both (rob, skip), because the parent needs the skip value.
Why must each node return BOTH the rob and skip values, not just the better one?
The parent needs the child's skip value. Robbing the parent forbids the children, so it adds their skip totals.
What is skip for a node, in terms of its children?
Skipping a node frees its children. Each child gives its own best.
“Max sum with no two directly-connected houses robbed.” A tree DP returning a pair.
Each node returns (rob, skip). rob = val + both children's skip. skip = each child's max(rob, skip), added up.
// Return (rob, skip); only the root collapses the pair. pair<int,int> solve(TreeNode* node) { if (!node) return {0, 0}; auto L = solve(node->left), R = solve(node->right); // .first = rob, .second = skip int rob = node->val + L.second + R.second; // rob node, children skipped int skip = max(L.first, L.second) + max(R.first, R.second); // children free return {rob, skip}; } int rob(TreeNode* root) { auto p = solve(root); return max(p.first, p.second); }
// Return (rob, skip) as a 2-slot array; only the root collapses the pair. int[] solve(TreeNode node) { if (node == null) return new int[]{0, 0}; int[] l = solve(node.left); int[] r = solve(node.right); int rob = node.val + l[1] + r[1]; // rob -> skip children int skip = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); // children free return new int[]{rob, skip}; } public int rob(TreeNode root) { int[] a = solve(root); return Math.max(a[0], a[1]); }
# Return (rob, skip); only the root collapses the pair. def rob(root): def solve(node): if not node: return (0, 0) lr, ln = solve(node.left) rr, rn = solve(node.right) do_rob = node.val + ln + rn # rob node -> skip children skip = max(lr, ln) + max(rr, rn) # skip node -> children free return (do_rob, skip) return max(solve(root))
Returning one max. The parent needs the child's skip value, which is lost once you collapse to max.
Three states: needs cover, covered, camera. Put a camera on a node only when a child is uncovered. The root fixes itself last.
Why does a null node return 'covered' (1), and what does that achieve for leaves?
Null counts as covered, so cameras go on parents of leaves. One camera there covers three levels.
After the postorder returns, why might you still need to add one camera at the root?
The root has no parent to rely on. If it ends uncovered, it gets its own camera.
“Fewest cameras so every node is monitored.” A 3-state greedy postorder.
States: 0 uncovered, 1 covered, 2 camera. Null is 1. A child at 0: camera here (2). A child at 2: covered (1). Else 0. Fix the root at the end.
// 3-state greedy: camera only when a child is uncovered. int cameras = 0; int dfs(TreeNode* node) { // 0 uncovered, 1 covered, 2 has camera if (!node) return 1; // null counts as covered int l = dfs(node->left), r = dfs(node->right); if (l == 0 || r == 0) { cameras++; return 2; } // must cover a child if (l == 2 || r == 2) return 1; // a child's camera covers us return 0; // uncovered -> parent handles } int minCameraCover(TreeNode* root) { cameras = 0; if (dfs(root) == 0) cameras++; // root left uncovered return cameras; }
// 3-state greedy: camera only when a child is uncovered. int cameras = 0; int dfs(TreeNode node) { // 0 uncovered, 1 covered, 2 has camera if (node == null) return 1; // null counts as covered int l = dfs(node.left), r = dfs(node.right); if (l == 0 || r == 0) { cameras++; return 2; } // must cover a child if (l == 2 || r == 2) return 1; // a child's camera covers us return 0; // uncovered: parent's job } public int minCameraCover(TreeNode root) { return (dfs(root) == 0 ? 1 : 0) + cameras; // root uncovered? one more }
# 3-state greedy: camera only when a child is uncovered. def minCameraCover(root): cameras = 0 def dfs(node): # 0 uncovered, 1 covered, 2 has camera nonlocal cameras if not node: return 1 # null counts as covered l, r = dfs(node.left), dfs(node.right) if l == 0 or r == 0: cameras += 1; return 2 # must cover an uncovered child if l == 2 or r == 2: return 1 # a child's camera covers us return 0 # uncovered -> parent handles it if dfs(root) == 0: cameras += 1 # root left uncovered return cameras
Cameras on leaves, or no root fix-up. Put cameras on parents of leaves. If the root ends uncovered, add one there.
Each card is the phrase in a statement that picks one technique.
left-height == right-height means a perfect subtree of 2^h − 1 nodes, no walk
COMPLETE-TREE SHORTCUTO(log²n)reuse the tree's own right pointers; thread the left subtree in before the right
IN-PLACE REWIREO(n) · O(1) spacepre/post gives the root, inorder splits left|right; recurse with an index map
RECONSTRUCT FROM SEQUENCESO(n)serialize with null markers (preorder or BFS); deserialize by consuming tokens
SERIALIZE + DESERIALIZEO(n)point the inorder predecessor's null right pointer at the node, then undo it
MORRIS TRAVERSALO(n) · O(1) spaceeach node returns a small tuple of sub-answers; combine in one postorder
TREE DPO(n)Counting nodes in a COMPLETE binary tree in O(log²n): what shortcut avoids visiting every node?
Equal left and right heights ⇒ perfect, so use the formula. Only one path needs real recursion.
Binary Tree Cameras uses a greedy postorder with three node states. What are they, and when do you place a camera?
Camera only when a child is uncovered. Nulls count as covered, so leaves start uncovered and their parents take the camera.
Finale bugs are quiet. Each one below gives a believable wrong tree or number.
Scanning inorder for every root is O(n) per node. Use a value→index map.
From the back, postorder gives roots root-right-left, so build the right subtree first.
Counting every node is O(n). Equal heights skip whole perfect subtrees: O(log²n).
Morris threads a node's predecessor back to it. Remove the thread on the second visit, or the tree loops forever.
Without a marker for every null, 1,2,3 fits many trees. Write # for each missing child.
Returning max(rob, skip) loses the skip value the parent needs.
Eight techniques, one page. The right column is the cue for each.
Structure gave fast counting; backwards traversals rebuilt and serialized trees; Morris walked in O(1) space; tree DP folded the tree in one postorder.
Deck 3 of 3.
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.