A binary tree travels as a string: its level-order values comma-joined, with "null" for each absent child of a present node and trailing nulls trimmed — [1,2,3,null,null,4,5] travels as "1,2,3,null,null,4,5", the empty tree as "". Given the wire string data, rebuild the tree and return its root. (Writing the serializer is the warm-up; the deserializer, which must reconstruct shape from the flat stream, is what the tests call.)
Examples
Example 1:
Input: data = "1,2,3,null,null,4,5"
Output: [1,2,3,null,null,4,5]
Example 2:
Input: data = ""
Output: []
Example 3:
Input: data = "7"
Output: [7]
Example 4:
Input: data = "1,2,null,3"
Output: [1,2,null,3]
Explanation: a left-leaning chain — position in the stream is everything.
Constraints
0 <= number of nodes <= 10^4
-1000 <= Node.val <= 1000
Prerequisites
Serialization — turning a structure into a flat sequence and back, and choosing a format that survives ambiguity.
How to think about it
1. Rebuild in the Order It Was Written Optimal
Intuition
Level order with explicit nulls is a complete description: position in the stream determines parentage, and the nulls are what make it unambiguous. Rebuilding runs the writer backwards — a queue of nodes waiting for children, each present node consuming the next two tokens. The symmetry between the two directions is the design point; preorder with markers is an equally valid format and worth naming.
Algorithm
1. Empty string: empty tree. 2. First token is the root; queue it. 3. For each queued node, consume the next two tokens as its children, queueing the non-null ones. 4. Running out of tokens means the remaining children are absent.