INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP
01
00/07
01 / COVER STEP 13 · BINARY TREES
INVARIANT · STEP 13 · DECK 3 OF 3
BUILD THE TREE

The finale: count a complete tree fast, rebuild and serialize trees, walk with Morris in O(1) space, and finish on tree DP.

7Problems
3Families
8Units
10Live 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 · CONSTRUCTION & TREE DP · DECK 3 OF 3
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 7 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.

STRUCTURE · 02
BUILD FROM TRAVERSALS · 03
TREE DP · 02
SOLVED HAS A LEETCODE LINK
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
03 / MECHANISM UNIT 01 · COUNT COMPLETE NODES

A PERFECT SUBTREE NEEDS NO WALK

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
04 / DRILL UNIT 01 · Count Complete Nodes

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · RECALL

Where does the O(log²n) come from?

O(log n) levels × O(log n) height walk. Each perfect subtree is answered by formula.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
05 / PROBLEM #01 · STRUCTURE · MED

Count Complete Tree Nodes

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

“Count nodes of a COMPLETE binary tree, better than O(n).” 'Complete' is the signal to exploit the shape.

INTUITION

Walk only left and only right. Equal heights mean the subtree is perfect: return 2^h − 1. Otherwise 1 + count(left) + count(right).

STEPS
  1. leftHeight(node): count nodes going only left; rightHeight: only right. Heights count nodes on the path, so the 7-node tree has height 3
  2. count(node): if null, return 0
  3. if leftHeight == rightHeight: return 2^leftHeight − 1 (perfect)
  4. else return 1 + count(left) + count(right)
↕ SCROLL
// 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);
}
TIMEO(log²n)O(log n) recursions, each an O(log n) height check
SPACEO(log n)recursion depth
TRAP

Counting every node, O(n). Use the equal-heights shortcut, so only one ragged path recurses: O(log²n).

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
06 / MECHANISM UNIT 02 · BUILD FROM PRE + IN

INORDER IS WHAT SPLITS THE PROBLEM

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
07 / DRILL UNIT 02 · Build from Pre + In

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

What role does each of the two traversals play in the reconstruction?

Preorder gives the root; inorder gives the split.

DRILL 02 · RECALL

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.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
08 / PROBLEM #02 · BUILD · MED

Construct Binary Tree from Preorder and Inorder Traversal

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

“Reconstruct the tree from preorder + inorder.” Two sequences, one unique tree.

INTUITION

Preorder's front is the root. Find it in inorder (with a value→index map) to split left from right, then recurse.

STEPS
  1. build a map: inorder value → its index
  2. preIdx = 0
  3. build(inL, inR): if inL > inR, return null
  4. rootVal = preorder[preIdx++]; mid = map[rootVal]
  5. node->left = build(inL, mid−1); node->right = build(mid+1, inR); return node
↕ SCROLL
// 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);
}
TIMEO(n)each node created once with O(1) split lookups
SPACEO(n)the index map + recursion
TRAP

Scanning inorder for the root every call: O(n²). Precompute a value→index map, and build left before right.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
09 / MECHANISM UNIT 03 · BUILD FROM IN + POST

READ POSTORDER FROM THE BACK, BUILD RIGHT FIRST

Postorder's last value is the root. Read it backwards: take roots from the back and build the right side first.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
10 / DRILL UNIT 03 · Build from In + Post

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · RECALL

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.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
11 / PROBLEM #03 · BUILD · MED

Construct Binary Tree from Inorder and Postorder Traversal

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

“Reconstruct the tree from inorder + postorder.” Same idea, postorder from the back.

INTUITION

Postorder's last value is the root. Read it from the back: roots come root-right-left, so build the RIGHT subtree first.

STEPS
  1. build a map: inorder value → its index
  2. postIdx = postorder.size() − 1
  3. build(inL, inR): if inL > inR, return null
  4. rootVal = postorder[postIdx--]; mid = map[rootVal]
  5. node->right = build(mid+1, inR); node->left = build(inL, mid−1); return node
↕ SCROLL
// 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);
}
TIMEO(n)each node created once with O(1) split lookups
SPACEO(n)the index map + recursion
TRAP

Building left before right. From the back, the next roots belong to the right subtree.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
12 / MECHANISM UNIT 04 · SERIALIZE & DESERIALIZE

THE NULL MARKERS ARE THE ENCODING

Values alone can't be read back. Write preorder with a # for every missing child; those markers are the shape.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
13 / MECHANISM UNIT 04 · SERIALIZE & DESERIALIZE

READ IT BACK IN THE SAME ORDER

Read the tokens front to back. A number makes a node and builds its left, then its right; a # is an empty child.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
14 / DRILL UNIT 04 · Serialize & Deserialize

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why are null markers essential in the serialized string?

Markers fix the shape. The values 1,2,3 alone fit many trees.

DRILL 02 · RECALL

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.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
15 / PROBLEM #04 · BUILD · HARD

Serialize and Deserialize Binary Tree

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

“Serialize a tree to a string and deserialize it back.” Encode with null markers.

INTUITION

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.

STEPS
  1. serialize: preorder dfs; append val + ',' or '#,' for null
  2. deserialize: split into tokens; use an index/queue
  3. read a token: '#' → null; else create node(token)
  4. node->left = build(); node->right = build(); return node
↕ SCROLL
// 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); }
TIMEO(n)each node emitted and read once
SPACEO(n)the string + recursion
TRAP

No null markers. Without a '#' for every missing child, many trees give the same string.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
16 / MECHANISM UNIT 05 · MORRIS TRAVERSAL

BORROW A NULL POINTER TO CLIMB BACK UP

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
17 / DRILL UNIT 05 · Morris Traversal

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · RECALL

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.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
18 / MECHANISM UNIT 06 · FLATTEN TO LINKED LIST

BUILD THE CHAIN FROM THE TAIL BACKWARDS

Recurse right, then left, then link the node in front of the finished tail in prev. Nothing is overwritten before it is used.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
19 / MECHANISM UNIT 06 · FLATTEN TO LINKED LIST

MOVE THE LEFT SUBTREE OVER, HANG THE RIGHT ONE UNDER IT

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
20 / DRILL UNIT 06 · Flatten to Linked List

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · RECALL

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.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
21 / PROBLEM #05 · STRUCTURE · MED

Flatten Binary Tree to Linked List

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

“Flatten the tree to a right-skewed linked list, preorder order, in place.” O(1) space via a Morris-like rewire.

INTUITION

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.

STEPS
  1. cur = root
  2. while cur: if cur->left is not null:
  3. rightmost = cur->left; while rightmost->right: rightmost = rightmost->right // rightmost of left
  4. rightmost->right = cur->right; cur->right = cur->left; cur->left = null
  5. cur = cur->right
↕ SCROLL
// 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
    }
}
TIMEO(n)the inner loop walks each right pointer at most once in the whole run
SPACEO(1)no auxiliary storage
TRAP

Collecting preorder into a list first: O(n) space. Rewire in place, and remember to clear the left pointer.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
22 / MECHANISM UNIT 07 · HOUSE ROBBER III

ONE NUMBER PER NODE IS NOT ENOUGH

No two robbed houses may share an edge. Each node returns both (rob, skip), because the parent needs the skip value.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
23 / DRILL UNIT 07 · House Robber III

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · RECALL

What is skip for a node, in terms of its children?

Skipping a node frees its children. Each child gives its own best.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
24 / PROBLEM #06 · TREEDP · MED

House Robber III

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

“Max sum with no two directly-connected houses robbed.” A tree DP returning a pair.

INTUITION

Each node returns (rob, skip). rob = val + both children's skip. skip = each child's max(rob, skip), added up.

STEPS
  1. solve(node): if null, return (0, 0)
  2. L = solve(left); R = solve(right) // .first = rob, .second = skip
  3. rob = node->val + L.skip + R.skip // children skipped
  4. skip = max(L.rob, L.skip) + max(R.rob, R.skip) // children free
  5. return (rob, skip); answer = max of the root's pair
↕ SCROLL
// 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);
}
TIMEO(n)each node visited once, O(1) combine
SPACEO(h)recursion depth
TRAP

Returning one max. The parent needs the child's skip value, which is lost once you collapse to max.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
25 / MECHANISM UNIT 08 · BINARY TREE CAMERAS

PUT THE CAMERA ON THE PARENT, NEVER THE LEAF

Three states: needs cover, covered, camera. Put a camera on a node only when a child is uncovered. The root fixes itself last.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
26 / DRILL UNIT 08 · Binary Tree Cameras

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · RECALL

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.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
27 / PROBLEM #07 · TREEDP · HARD

Binary Tree Cameras

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

“Fewest cameras so every node is monitored.” A 3-state greedy postorder.

INTUITION

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.

STEPS
  1. cameras = 0
  2. dfs(node): if null, return 1 (covered)
  3. l = dfs(left); r = dfs(right)
  4. if l == 0 or r == 0: cameras++; return 2 (place a camera)
  5. if l == 2 or r == 2: return 1 (covered); else return 0 (uncovered)
  6. answer: if dfs(root) == 0, cameras++; return cameras
↕ SCROLL
// 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;
}
TIMEO(n)each node visited once
SPACEO(h)recursion depth
TRAP

Cameras on leaves, or no root fix-up. Put cameras on parents of leaves. If the root ends uncovered, add one there.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
28 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH TECHNIQUE, AND WHY

Each card is the phrase in a statement that picks one technique.

“COMPLETE TREE” + “COUNT NODES FAST”

left-height == right-height means a perfect subtree of 2^h − 1 nodes, no walk

COMPLETE-TREE SHORTCUTO(log²n)
“FLATTEN” / “REARRANGE INTO A LIST”

reuse the tree's own right pointers; thread the left subtree in before the right

IN-PLACE REWIREO(n) · O(1) space
“BUILD THE TREE FROM ITS TRAVERSALS”

pre/post gives the root, inorder splits left|right; recurse with an index map

RECONSTRUCT FROM SEQUENCESO(n)
“SEND A TREE / STORE IT AS A STRING”

serialize with null markers (preorder or BFS); deserialize by consuming tokens

SERIALIZE + DESERIALIZEO(n)
“INORDER IN O(1) SPACE” / NO STACK, NO RECURSION

point the inorder predecessor's null right pointer at the node, then undo it

MORRIS TRAVERSALO(n) · O(1) space
“MAX/MIN OVER THE TREE WITH A CONSTRAINT” (no two adjacent…)

each node returns a small tuple of sub-answers; combine in one postorder

TREE DPO(n)
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
29 / RECALL RETRIEVAL, NOT RECOGNITION

NAME THE TECHNIQUE FROM THE STATEMENT

DRILL 01 · TRANSFER

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.

DRILL 02 · RECALL

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.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
30 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

Finale bugs are quiet. Each one below gives a believable wrong tree or number.

CONSTRUCTION: LINEAR SEARCH FOR THE ROOT ⇒ O(n²)

Scanning inorder for every root is O(n) per node. Use a value→index map.

IN+POST: BUILDING THE LEFT SUBTREE BEFORE THE RIGHT

From the back, postorder gives roots root-right-left, so build the right subtree first.

COUNT COMPLETE NODES: FALLING BACK TO AN O(n) WALK

Counting every node is O(n). Equal heights skip whole perfect subtrees: O(log²n).

MORRIS: NOT REMOVING THE THREAD

Morris threads a node's predecessor back to it. Remove the thread on the second visit, or the tree loops forever.

SERIALIZE: NO NULL MARKERS

Without a marker for every null, 1,2,3 fits many trees. Write # for each missing child.

TREE DP: COLLAPSING THE TUPLE TOO EARLY

Returning max(rob, skip) loses the skip value the parent needs.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
31 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Eight techniques, one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Count complete nodes
O(log²n)
O(log n)
equal left/right height ⇒ 2^h − 1; else recurse
Build from pre + in
O(n)
O(n)
preorder gives root; inorder index map splits left|right
Build from in + post
O(n)
O(n)
postorder (from back) gives root; build RIGHT then left
Serialize / deserialize
O(n)
O(n)
preorder (or BFS) with # null markers; consume tokens
Morris inorder
O(n)
O(1)
predecessor's right points back at node; visit; undo
Flatten to list
O(n)
O(1)
attach right subtree to the left subtree's rightmost, move left→right
House Robber III
O(n)
O(h)
return (rob, skip); rob = val + skip(children)
Binary Tree Cameras
O(n)
O(h)
3-state greedy; camera when a child is uncovered
INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
32 / CLOSE STEP 13 · DECK 3 OF 3

BUILD THE TREE

Structure gave fast counting; backwards traversals rebuilt and serialized trees; Morris walked in O(1) space; tree DP folded the tree in one postorder.

00%
OF THIS DECK SOLVED
← ALL TOPICS← DECK 1 · TRAVERSALS← DECK 2 · PROPERTIES

Deck 3 of 3.

INVARIANT · BINARY TREES · CONSTRUCTION & TREE DP · DECK 3 OF 3
■ TOO SMALL TO READ
1280×720
INVARIANT · STEP 13 · DECK 3 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.