Recursion and Trees
Writing a tree down and reading it back
The framing problem from Unit 1, now with structure instead of a flat list.
Key idea
You have met this problem before
In Unit 1 you framed a list of strings so it could be split back apart, and the lesson was that a reader must never have to guess where something ends.
This is that problem with a tree. The extra difficulty is that a tree has shape as well as contents, and the shape has to survive the round trip.
Why it works
Record the empty children
The previous lesson established that one traversal does not determine a tree. That is true of traversals that skip empty children. Once every absent child is written down explicitly, a single pre-order traversal does determine the tree.
The markers are what supply the missing information. They tell the reader exactly where each branch stops, which is the same job the length prefix did in Unit 1.
There is a cost, and it is worth knowing before you write anything. Every node has two child slots, so a tree of n nodes has exactly n plus 1 slots that are empty.
Why it works
Reading it back is the same traversal
The reader consumes tokens in the order they were written and rebuilds in the same pre-order shape. Take a token: if it is the marker, this branch is empty; otherwise make a node, then build its left subtree, then its right.
The recursion consumes exactly the tokens belonging to each subtree and leaves the rest, which is what makes the second call pick up in the right place. That property is the whole reason this works, and it is worth convincing yourself of by hand on a three-token stream before trusting it on a large one.
Everything rests on the position being shared, so watch that on its own before assembling anything.
Gotcha
The reader's position must be shared
The reader keeps its own position and every recursive call advances the same one. Passing an index by value instead, and returning it alongside the node, also works but is easy to get wrong.
What does not work is each call starting from the beginning. If a rebuilt tree comes back with repeated subtrees, that is the cause.
Edge cases
Choose a separator the values cannot contain
Joining with commas is fine when values are integers. It breaks the moment a value could contain a comma, which is exactly the failure from Unit 1.
If values are arbitrary, go back to length prefixing. The technique composes: frame each token by length, then frame the sequence of tokens. Recognizing that these are the same problem at two scales is the point of putting them in the same course.
Tip
A breadth-first alternative
Level-order serialization with markers also works and is what most textual tree formats use, because it reads more naturally to a human.
It needs a queue on both sides rather than recursion, and the marker handling is fiddlier. Either is a fine answer; say which you chose and why.
Predict the output: with and without the empty markers
Two different trees are written down in preorder. One version records nothing for an absent child; the other writes a #. Type the four lines it prints.
Serialize And Deserialize Binary Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.