Pack and Ship a Tree

hard

Two services need to hand a binary tree across a network that only carries strings. You own both ends of the pipe: design serialize(root), which flattens a tree into a single string, and deserialize(data), which rebuilds an identical tree from that string. Any encoding you like — it only has to survive the round trip, including missing children and negative values.

Tests check the round trip: the grader builds a tree from a level-order array, runs it through your serialize then deserialize, and compares the rebuilt tree's level-order form against the original.

Example 1

in values = [1, 2, 3, null, null, 4, 5]

out [1, 2, 3, null, null, 4, 5]

Whatever string you produce in between, the rebuilt tree must match the original.

Example 2

in values = []

out []

Example 3

in values = [1, null, 2, null, 3]

out [1, null, 2, null, 3]

A right-leaning chain — your encoding must capture missing left children.

Constraints

· 0 <= number of nodes <= 10^4
· -1000 <= node value <= 1000
· serialize must return a str; deserialize must accept exactly that str