Building and Serializing Trees
One list loses the shape
A traversal writes a tree down as a list. One list isn't enough to get the tree back: the preorder 1, 2, 3 is a chain going left, a chain going right, a zigzag either way, or a root with two children. Five trees, one list. Two lists can be enough, depending on which two:
| Two lists | Fix the tree? | Why |
|---|---|---|
| Preorder and inorder | Yes | preorder names each root; the inorder puts its left subtree before it and its right after |
| Inorder and postorder | Yes | postorder names each root, last; the inorder splits the same way |
| Preorder and postorder | Not always | they name the roots, but nothing says which side a lone child is on |
| One list with a mark for every missing child | Yes | the marks say where each subtree ends |
Counted on every tree shape of up to 7 nodes: preorder with inorder told all 429 seven-node shapes apart. Preorder with postorder told only 51 apart, and one pair of lists fitted 64 different trees. Everything in this lesson is about what a list keeps:
Preorder finds the root, the inorder splits it
Take the tree's preorder [1, 2, 4, 5, 7, 3, 6] and inorder [4, 2, 7, 5, 1, 3, 6]. Preorder lists a root before anything below it, so 1 is the root. In the inorder, everything in 1's left subtree comes before 1 and everything in its right subtree after it: [4, 2, 7, 5] on the left, [3, 6] on the right. The left part has 4 values, so the 4 preorder values after the root, [2, 4, 5, 7], are the left subtree's own preorder, and [3, 6] the right's. Each half is the same problem again.
Searching the inorder for each root costs a pass. A map from each value to its place in the inorder makes it one lookup. And the next root is always the next preorder value, since the left subtree is built before the right, so one index walks the preorder from front to back with no copies:
// Preorder gives each root; its place in the inorder splits the left subtree from the right.
TreeNode* buildTree(const vector<int>& preorder, const vector<int>& inorder) {
unordered_map<int, int> at; // each value's place in the inorder
for (int k = 0; k < (int)inorder.size(); k++) at[inorder[k]] = k;
int next = 0; // the next preorder value is the next root
function<TreeNode*(int, int)> grow = [&](int lo, int hi) -> TreeNode* {
if (lo > hi) return nullptr; // an empty part of the inorder: no subtree
TreeNode* root = new TreeNode(preorder[next++]);
int k = at[root->val];
root->left = grow(lo, k - 1); // what's left of the root in the inorder
root->right = grow(k + 1, hi); // and what's right of it
return root;
};
return grow(0, (int)inorder.size() - 1);
}
import sys
sys.setrecursionlimit(10_000) # a 3,000-node tree that leans one way is 3,000 calls deep
def build_tree(preorder, inorder):
"""Preorder gives each root; its place in the inorder splits the left subtree from the right."""
at = {v: k for k, v in enumerate(inorder)} # each value's place in the inorder
next_root = 0 # the next preorder value is the next root
def grow(lo, hi):
nonlocal next_root
if lo > hi: # an empty part of the inorder: no subtree
return None
root = TreeNode(preorder[next_root])
next_root += 1
k = at[root.val]
root.left = grow(lo, k - 1) # what's left of the root in the inorder
root.right = grow(k + 1, hi) # and what's right of it
return root
return grow(0, len(inorder) - 1)
// Preorder gives each root; its place in the inorder splits the left subtree from the right.
static int next; // the next preorder value is the next root
static Map<Integer, Integer> at; // each value's place in the inorder
static TreeNode buildTree(int[] preorder, int[] inorder) {
at = new HashMap<>();
for (int k = 0; k < inorder.length; k++) at.put(inorder[k], k);
next = 0;
return grow(preorder, 0, inorder.length - 1);
}
static TreeNode grow(int[] preorder, int lo, int hi) {
if (lo > hi) return null; // an empty part of the inorder: no subtree
TreeNode root = new TreeNode(preorder[next++]);
int k = at.get(root.val);
root.left = grow(preorder, lo, k - 1); // what's left of the root in the inorder
root.right = grow(preorder, k + 1, hi); // and what's right of it
return root;
}
// Preorder gives each root; its place in the inorder splits the left subtree from the right.
function buildTree(preorder, inorder) {
const at = new Map(inorder.map((v, k) => [v, k])); // each value's place in the inorder
let next = 0; // the next preorder value is the next root
const grow = (lo, hi) => {
if (lo > hi) return null; // an empty part of the inorder: no subtree
const root = new TreeNode(preorder[next++]);
const k = at.get(root.val);
root.left = grow(lo, k - 1); // what's left of the root in the inorder
root.right = grow(k + 1, hi); // and what's right of it
return root;
};
return grow(0, inorder.length - 1);
}
Each printed the tree as LeetCode's list: [3, 9, 20, null, null, 15, 7] for the problem's first example, [-1] for its one-node tree, and [1, 2, 3, 4, 5, null, 6, null, null, 7] for ours. Every node is made once and every lookup is one step: O(n) time, and O(n) for the map. The values must be unique, or a value would have two places in the inorder.
The recursion is as deep as the tree. A 3,000-node tree that leans one way, the problem's largest, is 3,000 calls deep, past Python's limit of about 1,000 (Introduction to Binary Trees measured it), so the Python version raises it.
Without the map, each root is found by searching, and the usual Python for that also slices both lists at every call. On trees that lean left, where each search runs to the end of its part:
| Nodes | Searching, with slices | A map of positions |
|---|---|---|
| 1,000 | 28.2 ms | 1.24 ms |
| 2,000 | 112.9 ms | 2.71 ms |
| 3,000 | 245.5 ms | 4.29 ms |
| 3,000, a random shape | 4.8 ms | 4.19 ms |
Both built the same tree every time. Doubling the nodes roughly quadruples the search; on a random tree, shallow and bushy, the two are close. With the map, the leaning tree builds as fast as the bushy one.
Now you split the inorder
Below, you rebuild a tree from two of its lists. The amber values are the part being built, the same values in both lists, and the amber node in the tree is where its root goes. Its root is the first amber value of the preorder: click it in the inorder. Everything left of it there becomes its left subtree, everything right of it its right subtree. A wrong click is refused, with the reason. Then switch to postorder and inorder, where each root is the last amber value.
Inorder and postorder, and the pair that can't
Postorder lists a root after everything below it, so the root is the last value. Read from the back, postorder gives a root, then all of its right subtree, then all of its left. The same split works; the right subtree is built first:
def build_tree(inorder, postorder):
"""Postorder lists each root last. Read from the back, it gives a root, then its right subtree's roots."""
at = {v: k for k, v in enumerate(inorder)}
next_root = len(postorder) - 1
def grow(lo, hi):
nonlocal next_root
if lo > hi:
return None
root = TreeNode(postorder[next_root])
next_root -= 1
k = at[root.val]
root.right = grow(k + 1, hi) # the right subtree first: its roots come next
root.left = grow(lo, k - 1)
return root
return grow(0, len(inorder) - 1)
It printed [3, 9, 20, null, null, 15, 7] for Construct Binary Tree from Inorder and Postorder Traversal's first example, and [1, 2, 3, 4, 5, null, 6, null, null, 7] from our tree's inorder and postorder [4, 7, 5, 2, 6, 3, 1].
Preorder with postorder names every root, from both ends, and still can't place a node with one child: in both lists the child comes straight after (or before) its parent whichever side it hangs on. The three-node chains show it:
Of the five shapes with 3 nodes, four share that pair. In general, a pair is shared by 2^s trees, where s is the number of nodes with one child: the count above held for every one of the 429 shapes with 7 nodes. When every node has 0 or 2 children, there's no lone child to place, and preorder with postorder does fix the tree (Construct Binary Tree from Preorder and Postorder Traversal asks for any tree that fits).
Conditions for Unique Tree Construction asks exactly this, with 1 for preorder, 2 for inorder and 3 for postorder:
def is_possible(a, b):
"""1 is preorder, 2 inorder, 3 postorder: two lists fix a tree when exactly one of them is the inorder."""
return int((a == 2) != (b == 2))
Of the nine pairs, it said yes to (1, 2), (2, 1), (2, 3) and (3, 2): one of the two must be the inorder, and two inorders tell you nothing about the roots.
Writing a tree down
Serialize and Deserialize Binary Tree asks for a string that holds a whole tree, and a way to read it back. One traversal is enough once every missing child is written as a mark: the marks say where each subtree ends, so nothing is left to guess. Preorder with a # for each missing child, read back in the same order:
class Codec:
def serialize(self, root):
"""Preorder, with '#' for every missing child: the marks say where each subtree ends."""
out = []
def write(node):
if node is None:
out.append("#")
return
out.append(str(node.val))
write(node.left)
write(node.right)
write(root)
return ",".join(out)
def deserialize(self, data):
"""Read it back in the same order: each call takes a value and builds its two subtrees, or takes a '#'."""
values = iter(data.split(","))
def read():
v = next(values)
if v == "#":
return None
node = TreeNode(int(v))
node.left = read()
node.right = read()
return node
return read()
LeetCode's first example came out as 1,2,#,#,3,4,#,#,5,#,#: 1, then 2 with no children, then 3 with 4 and 5. It read back to the same tree, and the empty tree went to # and back.
Both halves recurse as deep as the tree, and the problem allows 10,000 nodes, which can be one long chain. Run on chains, the recursive serialize gave out in three of the four languages:
| Language | On a chain of 10,000 nodes | What it took |
|---|---|---|
| Python | failed | failed at 1,000 nodes and passed at 900: its limit is about 1,000 calls |
| Java | failed | ran out of stack after about 9,860 calls |
| JavaScript | failed on a fresh run | its limit sits near 10,000 and moves as the code warms up; warmed up, it passed |
| C++ | passed | its stack held all 10,000 calls |
Level order needs no recursion. It is also LeetCode's own format: a queue writes the tree level by level with a mark for each missing child, and reading it back is the queue of parents from Introduction to Binary Trees, each taking the next two entries as its children:
class Codec {
public:
// Level by level, '#' for every missing child: LeetCode's own format, with no recursion.
string serialize(TreeNode* root) {
string out;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (!out.empty()) out += ',';
if (!node) {
out += '#';
continue;
}
out += to_string(node->val);
q.push(node->left);
q.push(node->right);
}
return out;
}
// The same order back: each node in the queue takes the next two entries as its children.
TreeNode* deserialize(string data) {
vector<string> values;
stringstream ss(data);
for (string v; getline(ss, v, ',');) values.push_back(v);
if (values[0] == "#") return nullptr;
TreeNode* root = new TreeNode(stoi(values[0]));
queue<TreeNode*> q;
q.push(root);
size_t i = 1;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (values[i] != "#") {
node->left = new TreeNode(stoi(values[i]));
q.push(node->left);
}
if (values[i + 1] != "#") {
node->right = new TreeNode(stoi(values[i + 1]));
q.push(node->right);
}
i += 2;
}
return root;
}
};
from collections import deque
class Codec:
def serialize(self, root):
"""Level by level, '#' for every missing child: LeetCode's own format, with no recursion."""
out, queue = [], deque([root])
while queue:
node = queue.popleft()
if node is None:
out.append("#")
continue
out.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
return ",".join(out)
def deserialize(self, data):
"""The same order back: each node in the queue takes the next two entries as its children."""
values = data.split(",")
if values[0] == "#":
return None
root = TreeNode(int(values[0]))
queue, i = deque([root]), 1
while queue:
node = queue.popleft()
if values[i] != "#":
node.left = TreeNode(int(values[i]))
queue.append(node.left)
if values[i + 1] != "#":
node.right = TreeNode(int(values[i + 1]))
queue.append(node.right)
i += 2
return root
static class Codec {
// Level by level, '#' for every missing child: LeetCode's own format, with no recursion.
public String serialize(TreeNode root) {
StringBuilder out = new StringBuilder(); // not +=, which copies the whole string each time
Queue<TreeNode> queue = new LinkedList<>(); // it holds nulls, which an ArrayDeque refuses
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (out.length() > 0) out.append(',');
if (node == null) {
out.append('#');
continue;
}
out.append(node.val);
queue.add(node.left);
queue.add(node.right);
}
return out.toString();
}
// The same order back: each node in the queue takes the next two entries as its children.
public TreeNode deserialize(String data) {
String[] values = data.split(",");
if (values[0].equals("#")) return null;
TreeNode root = new TreeNode(Integer.parseInt(values[0]));
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int i = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (!values[i].equals("#")) {
node.left = new TreeNode(Integer.parseInt(values[i]));
queue.add(node.left);
}
if (!values[i + 1].equals("#")) {
node.right = new TreeNode(Integer.parseInt(values[i + 1]));
queue.add(node.right);
}
i += 2;
}
return root;
}
}
// Level by level, '#' for every missing child: LeetCode's own format, with no recursion.
var serialize = function (root) {
const out = [];
const queue = [root];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
if (node === null) {
out.push("#");
continue;
}
out.push(String(node.val));
queue.push(node.left, node.right);
}
return out.join(",");
};
// The same order back: each node in the queue takes the next two entries as its children.
var deserialize = function (data) {
const values = data.split(",");
if (values[0] === "#") return null;
const root = new TreeNode(Number(values[0]));
const queue = [root];
let i = 1;
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
if (values[i] !== "#") {
node.left = new TreeNode(Number(values[i]));
queue.push(node.left);
}
if (values[i + 1] !== "#") {
node.right = new TreeNode(Number(values[i + 1]));
queue.push(node.right);
}
i += 2;
}
return root;
};
Each wrote and read back the problem's example, the empty tree and a tree with negative values: 1,2,3,#,#,4,5,#,#,#,#, # and -1,0,1000,#,-1000,#,#,#,#. The commas keep -1000 one value, and every string read back to the tree it came from. A tree of n nodes has n + 1 missing children, so the string holds 2n + 1 entries: O(n) to write and to read.
Flattening a tree in place
The last two problems here work on the tree itself, not on its lists, and each uses what a traversal order says about the tree's shape. Flatten Binary Tree to Linked List wants the nodes in preorder along the right pointers, every left pointer empty, with no new nodes. Preorder puts a node's left subtree straight after the node and its right subtree after the left one's last node. So for each node with a left subtree: find that subtree's last node in preorder, which is its rightmost, hang the right subtree off it, and move the left subtree to the right. Then go one step right and repeat:
// Preorder along the right pointers, in place: each left subtree moves to the right, and the old
// right subtree hangs off the left subtree's last node.
void flatten(TreeNode* root) {
for (TreeNode* node = root; node != nullptr; node = node->right) {
if (node->left == nullptr) continue;
TreeNode* last = node->left; // the left subtree's last node in preorder: its rightmost
while (last->right != nullptr) last = last->right;
last->right = node->right; // the right subtree comes after it
node->right = node->left; // the left subtree comes straight after the node
node->left = nullptr;
}
}
def flatten(root):
"""Preorder along the right pointers, in place: each left subtree moves to the right, and the old right
subtree hangs off the left subtree's last node."""
node = root
while node:
if node.left:
last = node.left # the left subtree's last node in preorder: its rightmost
while last.right:
last = last.right
last.right = node.right # the right subtree comes after it
node.right = node.left # the left subtree comes straight after the node
node.left = None
node = node.right
// Preorder along the right pointers, in place: each left subtree moves to the right, and the old
// right subtree hangs off the left subtree's last node.
static void flatten(TreeNode root) {
for (TreeNode node = root; node != null; node = node.right) {
if (node.left == null) continue;
TreeNode last = node.left; // the left subtree's last node in preorder: its rightmost
while (last.right != null) last = last.right;
last.right = node.right; // the right subtree comes after it
node.right = node.left; // the left subtree comes straight after the node
node.left = null;
}
}
// Preorder along the right pointers, in place: each left subtree moves to the right, and the old
// right subtree hangs off the left subtree's last node.
function flatten(root) {
for (let node = root; node !== null; node = node.right) {
if (node.left === null) continue;
let last = node.left; // the left subtree's last node in preorder: its rightmost
while (last.right !== null) last = last.right;
last.right = node.right; // the right subtree comes after it
node.right = node.left; // the left subtree comes straight after the node
node.left = null;
}
}
Each printed [1, null, 2, null, 3, null, 4, null, 5, null, 6] for the problem's first example, the chain written as LeetCode's list, then the empty tree and a single node unchanged. Step through it:
Rewiring 1, 2, 5, 3, 4, null, 6 — Indigo is the node being rewired; amber the walk down its left subtree's right edge; green that subtree's last node, where the right subtree is hung; violet the finished chain.
Each edge is walked at most twice, once by a search for a rightmost node and once by the main walk: O(n) time, O(1) extra space, and no recursion.
The recursive version flattens both subtrees first, then walks to the end of the flattened left part to attach the right one. On a tree that leans left, that walk gets longer at every level:
| Nodes | Recursing, then walking to the end | Rewiring in place |
|---|---|---|
| 1,000 | 18.9 ms | 0.36 ms |
| 2,000 | 73.5 ms | 0.72 ms |
| 2,000, a random shape | 1.2 ms | 0.73 ms |
Both produced the same chain every time.
Counting a complete tree without visiting it
Count Complete Tree Nodes gives a complete tree: every level full except perhaps the last, which fills from the left. A walk counts it in O(n), and the problem asks for better. In a complete tree, if a node's leftmost path and rightmost path have the same length h, its subtree is perfect and holds 2^h - 1 nodes with no walk at all. If they differ, the last level ends somewhere inside, and one of the node's two halves is still perfect:
// In a complete tree, a subtree whose leftmost and rightmost paths are as long as each other is
// perfect: 2^h - 1 nodes. Otherwise one of its two halves is perfect, and the calls go down one path.
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
int left = 0, right = 0;
for (TreeNode* n = root; n; n = n->left) left++;
for (TreeNode* n = root; n; n = n->right) right++;
if (left == right) return (1 << left) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
def count_nodes(root):
"""In a complete tree, a subtree whose leftmost and rightmost paths are as long as each other is perfect:
2^h - 1 nodes. Otherwise one of its two halves is perfect, and the calls go down one path."""
if root is None:
return 0
left, node = 0, root
while node:
left += 1
node = node.left
right, node = 0, root
while node:
right += 1
node = node.right
if left == right:
return (1 << left) - 1
return 1 + count_nodes(root.left) + count_nodes(root.right)
// In a complete tree, a subtree whose leftmost and rightmost paths are as long as each other is
// perfect: 2^h - 1 nodes. Otherwise one of its two halves is perfect, and the calls go down one path.
static int countNodes(TreeNode root) {
if (root == null) return 0;
int left = 0, right = 0;
for (TreeNode n = root; n != null; n = n.left) left++;
for (TreeNode n = root; n != null; n = n.right) right++;
if (left == right) return (1 << left) - 1;
return 1 + countNodes(root.left) + countNodes(root.right);
}
// In a complete tree, a subtree whose leftmost and rightmost paths are as long as each other is
// perfect: 2^h - 1 nodes. Otherwise one of its two halves is perfect, and the calls go down one path.
function countNodes(root) {
if (root === null) return 0;
let left = 0, right = 0;
for (let n = root; n !== null; n = n.left) left++;
for (let n = root; n !== null; n = n.right) right++;
if (left === right) return (1 << left) - 1;
return 1 + countNodes(root.left) + countNodes(root.right);
}
Each printed 6, 0, 1 and 12: the problem's examples and our 12-node tree. Only one child of each call can be imperfect, so the calls follow one path down, each walking two paths of O(log n): O(log² n) in all. On complete trees of the problem's size:
| Nodes | A full walk | Comparing the two paths |
|---|---|---|
| 12,500 | 12,500 visits, 3.03 ms | 27 calls, 0.031 ms |
| 25,000 | 25,000 visits, 6.29 ms | 29 calls, 0.035 ms |
| 50,000 | 50,000 visits, 12.49 ms | 31 calls, 0.039 ms |
Doubling the nodes adds one level, and two more calls.
In your language
Each language has one trap in this lesson's code, each run on the judge:
| Language | The trap | What happened |
|---|---|---|
| Python | recursion stops at about 1,000 calls | the recursive serialize failed on a chain of 1,000 nodes; raise the limit, or use a queue |
| Java | String += copies the whole string every time | serializing 10,000 nodes took 241.7 ms, against 7.07 ms with a StringBuilder |
| JavaScript | the stack runs out near 10,000 calls | the recursive serialize failed on a chain of 10,000 in a fresh run; the queue version has no limit |
| C++ | stoi("#") throws | reading a mark as a number stopped the program with std::invalid_argument: compare it to "#" first |
Java's cost grows with the square of the string: 21.8 ms at 2,500 nodes, 82.7 ms at 5,000 nodes, 241.7 ms at 10,000 nodes, against 1.95 to 7.07 ms with a StringBuilder.
Spotting it, and when it breaks
The clues. "Construct", "rebuild", "from its traversals": preorder or postorder for the roots, the inorder to split, a map of positions. "Serialize", "encode", "store and restore": a mark for every missing child, in preorder or level order. "Flatten", "in place", "into a linked list": rewire as you walk. "Complete tree" with "faster than O(n)": compare the two outer paths.
The near-misses. Construct Binary Tree from Preorder and Postorder Traversal accepts any tree that fits, because there can be several. Building a binary search tree from its preorder needs no inorder at all, since the values say which side each goes (Binary Search Trees). Serializing a tree with any number of children writes each node's child count instead of marks.
When it breaks. Repeated values break the inorder lookup: a value can sit in two places. A tree that leans one way breaks recursion in Python, Java and JavaScript at the problems' own sizes; the level-order codec and the rewiring don't recurse.
Bugs that cost a submission
Slices one value short.
def build_tree(preorder, inorder):
if not preorder:
return None
root = TreeNode(preorder[0])
k = inorder.index(preorder[0])
root.left = build_tree(preorder[1:k], inorder[:k]) # one value short
root.right = build_tree(preorder[k:], inorder[k + 1:])
return root
On the problem's first example it stopped with ValueError: 9 is not in list. The left subtree's preorder is the k values after the root, preorder[1:k + 1]; one short, and the right side starts with a value that belongs on the left.
The left subtree first, from the back of the postorder.
def build_tree(inorder, postorder):
"""Postorder lists each root last. Read from the back, it gives a root, then its right subtree's roots."""
at = {v: k for k, v in enumerate(inorder)}
next_root = len(postorder) - 1
def grow(lo, hi):
nonlocal next_root
if lo > hi:
return None
root = TreeNode(postorder[next_root])
next_root -= 1
k = at[root.val]
root.left = grow(lo, k - 1)
root.right = grow(k + 1, hi)
return root
return grow(0, len(inorder) - 1)
From our tree's inorder and postorder it stopped with an IndexError instead of building [1, 2, 3, 4, 5, null, 6, null, null, 7]: each part was handed a root that wasn't in it, and the calls ran off the postorder. Read from the back, the value after a root is its right subtree's root.
No marks for missing children.
def serialize(root):
"""Preorder, values only."""
if root is None:
return ""
rest = [serialize(root.left), serialize(root.right)]
return ",".join([str(root.val)] + [r for r in rest if r])
[1, 2] and [1, null, 2] both came out as 1,2: 2 on the left and 2 on the right wrote the same string, and no reader can tell them apart.
Flattening without clearing the left pointer.
def flatten(root):
"""Preorder along the right pointers, in place: each left subtree moves to the right, and the old right
subtree hangs off the left subtree's last node."""
node = root
while node:
if node.left:
last = node.left # the left subtree's last node in preorder: its rightmost
while last.right:
last = last.right
last.right = node.right # the right subtree comes after it
node.right = node.left # the left subtree comes straight after the node
node = node.right
The right pointers held all 6 nodes in order, but 2 of them still had a left child. The problem checks that every left pointer is empty.
Trusting the leftmost path alone.
def count_nodes(root):
h, node = 0, root
while node: # only the leftmost path
h += 1
node = node.left
return (1 << h) - 1
On [1, 2, 3, 4, 5, 6] it returned 7; the tree has 6 nodes. The leftmost path is 3 long, but the last level isn't full: only when the rightmost path is as long is the tree perfect.
Check yourself
Quiz
1 / 7Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
In this order:
- Conditions for Unique Tree Construction: which pairs of lists fix a tree.
- Construct Binary Tree from Preorder and Inorder Traversal: roots from the front, splits from a map.
- Construct Binary Tree from Inorder and Postorder Traversal: roots from the back, the right subtree first.
- Serialize and Deserialize Binary Tree: a mark for every missing child.
- Flatten Binary Tree to Linked List: rewire as you walk.
- Count Complete Tree Nodes: two paths at each call.
Then the section's quiz, and after it Binary Search Trees: trees whose values are in order, so a search goes straight down.