Build and Serialize

What is this?

So far we've been reading trees — here we make them. That means building a new tree, drawing one out as a picture, or flattening one into a line of text so it can be saved or sent and then rebuilt later, exactly. It's like writing down assembly instructions for a piece of furniture so detailed that someone on the other side of the world can recreate it piece for piece. The secret is choosing an order to record things in that leaves zero ambiguity.

💡 Fun fact: Turning a tree into a string is called "serialization," the same idea that lets your browser save a web page or a game save your progress to disk. The make-or-break detail is recording the empty spots too — without those blank markers, many different trees would flatten to the same text and could never be told apart.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: These problems are about producing a tree or a representation of one, rather than just reading it. The unifying move is a recursive walk where structure drives the work: visit nodes in a fixed order, and let each node's position in the recursion tell you what to create, where to place it, or what to write down. Get the order and the position right, and building mirrors traversing.

The pattern

Construction is traversal run in reverse. When you read a tree you consume its nodes in some order; when you build or encode one, you emit or place nodes in that same order. The trick is choosing an order that is unambiguous — that lets you (or a later reader) recover exactly one tree.

Two reliable orders show up here. Parallel DFS walks two trees at once, pairing up nodes by identical position so you can combine them. Position-by-formula uses the fact that in a perfect binary tree a node's row and column are computable from its depth, so you can drop nodes into a grid without any extra bookkeeping. And for full round-tripping, preorder with explicit null markers records enough about the shape that decoding becomes a straightforward replay.

The problems

• Merge Two Binary Trees — parallel DFS: recurse on both trees together; where both have a node, sum them; where only one does, splice that subtree in wholesale.
• Print Binary Tree — compute the output grid's height and width from the tree's depth, then place each node at the column its position formula dictates so the layout reads like a real tree.
• Serialize and Deserialize Binary Tree — preorder DFS writing values plus null placeholders, so the marker stream encodes the shape; deserialize replays that stream in the same preorder to rebuild it.

Key takeaways

• Building is traversal in reverse — pick a node order that uniquely determines the tree, then emit or place in that order.
• Parallel DFS handles any "combine two trees by position" task in one pass.
• Null markers are what make a flat string round-trip — they carry the structure that values alone would lose.
• Why interviewers like it: serialization forces you to reason about what information uniquely identifies a tree, a deeper test than a plain traversal.

Order: Merge Two Binary Trees → Print Binary Tree → Serialize and Deserialize Binary Tree → Construct Binary Tree from Preorder and Inorder → Construct Binary Tree from Inorder and Postorder.