Write a tree down as text
Turn a binary tree into a single line of text by writing a preorder walk with a marker for every missing child, so the shape can be recovered later. About 12 minutes.
Record the gaps too
To save a tree as text you must record both the values and the shape. A preorder walk visits a node, then its left subtree, then its right subtree. If you only write the values, many different trees give the same line.
The fix: whenever the walk reaches an empty child, write a marker, here a hash sign. Now every node is followed by exactly its left subtree and its right subtree, and an empty subtree is one marker.
out = []
out.append("1")
out.append("#") # an empty child
text = ",".join(out)- text
- 5
Write 5. Go left.
Same walk as preorder
After writing the node, visit the left child, then the right child, with the same function. Collect the pieces in a list and join them with commas at the end, which is faster than gluing text repeatedly.
An empty tree is a single marker. The result for a tree of n nodes has n plus 1 hash signs. The next step reads this text back and rebuilds the tree.
text = ",".join(out) # glue once
A tree has 6 nodes. How many hash signs does its text contain?
- A7
- B6
- C5
Show the answer
7. A tree with n nodes has n plus 1 empty child slots.
Serialize a binary tree
Design the writing half of a tree codec. Given the root of a binary tree, return a string made by walking the tree in preorder and writing each node's value, or the character # for an empty child, with the entries separated by commas. An empty tree gives "#".
root = [1, 2, 3, null, null, 4, 5] → "1,2,#,#,3,4,#,#,5,#,#"
0 ≤ number of nodes ≤ 10,000 · -1,000 ≤ node.val ≤ 1,000