Problem. Given the pre-order and in-order traversals of a binary tree with unique values, rebuild the tree and return its root.
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
3
/ \
9 20
/ \
15 7
Two facts make it work. Pre-order lists the root first. In-order lists everything in the root's left subtree before it and the right subtree after it. So the first pre-order value is the root, its position in the in-order list splits the in-order list into left and right parts, and their sizes split the rest of the pre-order list the same way.
ML context. Rebuilding structure from traversals is how trees travel through flat formats: a parse tree stored as token sequences, a model's module tree saved as lists, a decision tree exported as arrays. Knowing which traversals determine a tree uniquely (and which don't, Change C) is what makes a serialisation format correct; lesson 10.13 designs one.