What signals in a problem statement indicate the Build / transform / serialize sub-pattern?

"invert", "flatten", "in place"; "construct the tree from its preorder and inorder traversal"; "serialize" / "deserialize"

Build / transform / serialize (Tree DFS Sub-pattern)

Q: What makes Build / transform / serialize different from other sub-patterns?

**Invert** swaps the children at every node; save one before overwriting it. **Flatten** relinks into a right-only list in preorder: keep the old right subtree before moving the left one over, or use the O(1)-space "hang the right subtree under the rightmost node of the left one" walk. **Construct from Preorder + Inorder** takes roots from preorder and splits with an index map. **Serialize** writes preorder **with null markers**, which makes the string unambiguous, and reads it back in the same order.

Change the tree's shape, or rebuild a tree from a description of it. Choose the visiting order so you never lose a pointer you still need.

Signals in the problem statement

›
"invert", "flatten", "in place"
›
"construct the tree from its preorder and inorder traversal"
›
"serialize" / "deserialize"

What makes it different

Invert swaps the children at every node; save one before overwriting it. Flatten relinks into a right-only list in preorder: keep the old right subtree before moving the left one over, or use the O(1)-space "hang the right subtree under the rightmost node of the left one" walk. Construct from Preorder + Inorder takes roots from preorder and splits with an index map. Serialize writes preorder with null markers, which makes the string unambiguous, and reads it back in the same order.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Invert Binary Tree
Basic Anchor·LeetCode #226
WalkthroughEasy
2
Flatten Binary Tree to Linked List
Medium·LeetCode #114
WalkthroughMedium
3
Construct Binary Tree from Preorder and Inorder Traversal
Medium·LeetCode #105
WalkthroughMedium
4
Serialize and Deserialize Binary Tree
Interview-Level·LeetCode #297
WalkthroughHard

Template

build-template.cpp

// Build from preorder + inorder: preorder gives the next root, its position
// in inorder splits the left and right subtrees.
TreeNode* build(vector<int>& pre, int& next, int lo, int hi, unordered_map<int, int>& pos) {
    if (lo > hi) return nullptr;                         // empty inorder range → no subtree
    int val = pre[next++];
    TreeNode* node = new TreeNode(val);
    int mid = pos[val];
    node->left = build(pre, next, lo, mid - 1, pos);     // left first: preorder is root, left, right
    node->right = build(pre, next, mid + 1, hi, pos);
    return node;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> pos;                         // value → index in inorder (values are unique)
    for (int i = 0; i < (int)inorder.size(); i++) pos[inorder[i]] = i;
    int next = 0;
    return build(preorder, next, 0, (int)inorder.size() - 1, pos);
}

Remember this · Tree DFS

Trigger

Paths, heights, diameters, validating structure, ancestors, anything "for every subtree".

Think

If my left and right children already gave me their answers, how do I build mine?

Key question

What does my recursive function return, and what do I pass down?

Lowest common ancestor