The Checkpoint
You are an engineer building a distributed ML training system. Decision trees are checkpointed to disk between training runs and restored exactly on resume. A valid checkpoint system must be a perfect bijection — the same tree structure must be recovered every time, even with duplicate values or skewed shapes.
Design a serialize and deserialize algorithm for binary trees. To verify correctness, return the inorder traversal of the deserialized tree.
The tree is given as a level-order list where null represents a missing node.
Example 1
[1, 2, 3, 4, 5, 6, 7][4, 2, 5, 1, 6, 3, 7]Perfect binary tree serialized as preorder with # nulls, deserialized back, inorder traversal returns sorted level values.
Example 2
[1, 2][2, 1]Left child only. Serialized: '1,2,#,#,#'. Deserialized back correctly — structure preserved.
Example 3
[1, None, 2][1, 2]Right child only. Same values as [1,2] but different structure — serialization must encode shape via # markers.
- ›0 <= number of nodes <= 1000
- ›-1000 <= node.val <= 1000
Loading question…