Serialize and Deserialize Binary Tree
Design two functions. serialize(root) turns a binary tree into a single string; deserialize(data) turns such a string back into a tree that is structurally identical to the original, with the same values in the same positions. The string format is entirely your choice — you are only required to be able to read back what you wrote. An empty tree must survive the round trip too. This is an ordinary binary tree: no ordering of values may be assumed.
- The number of nodes in the tree is in the range [0, 10⁴]
- -1000 <= Node.val <= 1000
- Values may repeat, and may be negative
- You choose the encoding; only the round trip is graded
root = [1,2,3,null,null,4,5]round trip reproduces [1,2,3,null,null,4,5]root = []round trip reproduces []root = [1,2,null,3]round trip reproduces [1,2,null,3]root = [7,7,7]round trip reproduces [7,7,7]A tree is a two-dimensional shape; a string is a line. Serialization asks how to flatten one into the other without losing anything, and deserialization asks how to read it back. The interesting question is what "without losing anything" actually requires.
Write out a pre-order traversal and hand it over: [1, 2]. The reader knows 1 is the root and 2 is its only child, but not which side it hangs on — the two shapes produce identical output. This is exactly the ambiguity from Construct Tree from Preorder and Inorder, and there we fixed it by supplying a second traversal, with in-order acting as the map of where each root splits.
That fix is unavailable here for two reasons. Values may repeat, and locating a root inside the in-order array by value needs uniqueness. And nothing obliges us to send two arrays — we control the format, so we can fix the ambiguity at its source instead.
Where did the information actually go? A traversal lists only the nodes that exist. When node 1 has one child, the output says nothing at all about the missing side, so the reader cannot tell which side is missing. The absences are real structure, and we simply failed to write them down.
So write them down. Emit a marker — say # — for every null link. Now [1, 2] becomes either 1,2,#,#,# (2 on the left, then 2's two nulls, then 1's right null) or 1,#,2,#,# (1's left null, then 2 with its two nulls). Different strings, no ambiguity.
# means "this subtree is empty, nothing more to consume." Every token is a self-contained instruction, so a left-to-right scan can rebuild the tree with no lookahead and no boundary arithmetic at all.def serialize(node):
if node is None:
return "#" # the gap is data too
return f"{node.val},{serialize(node.left)},{serialize(node.right)}"
def deserialize(data):
tokens = iter(data.split(",")) # read strictly left to right
def build():
tok = next(tokens) # consume exactly one token
if tok == "#":
return None # an empty subtree — consumes nothing more
node = Node(int(tok))
node.left = build() # the next tokens are the whole left subtree
node.right = build() # then the whole right subtree
return node
return build()Notice the symmetry: the writer recurses node, left, right, and the reader recurses node, left, right. The two functions have the same shape because the reader is replaying the writer's walk.
build must consume its token before recursing, and the two recursive calls must be assigned in that order — left, then right. The stream carries no positional information; correctness rests entirely on the reader consuming tokens in exactly the order the writer produced them. This is the same discipline as the shared backward index in Construct Tree from Inorder and Postorder, and it fails the same way: swap the two lines and you get a valid-looking tree that is silently mirrored. A subtlety in some languages: if you write Node(tok, build(), build()) the argument evaluation order may not be guaranteed, so bind the calls to named variables in separate statements.2,#,#, then 3's subtree → 3,4,#,#,5,#,#. The full string is1,2,#,#,3,4,#,#,5,#,#Reading it back, one token at a time:
- 1 → make node 1, then go build its left.
- 2 → make node 2, then build its left: # → null. Then its right: # → null. Node 2 is finished and returns as 1's left child.
- 3 → make node 3, build its left: 4, whose two tokens are # and #, so 4 is a leaf. Then 3's right: 5, likewise a leaf.
- Node 3 returns as 1's right child; the stream is exhausted; the tree is complete.
Eleven tokens for five nodes — six of them markers. That is the price of the format, and it is a bargain compared with sending two full traversals.
Serialization visits every node once and every null link once. A tree with N nodes has exactly N + 1 null links, so the string holds 2N + 1 tokens: O(N) time and O(N) output. Deserialization consumes each token once, also O(N), with O(H) recursion depth on top of the O(N) token list. A level-order (BFS) encoding with markers is an equally valid alternative — it produces the familiar LeetCode array format and avoids deep recursion — but the pre-order version is shorter and its reader needs no queue of pending parents.
The transferable principle is worth stating carefully, because it reaches well past trees: a structure can be flattened into a line without loss exactly when the reader can tell where each part ends. You get that either by sending a second view that pins down the boundaries (the two-traversal reconstructions), or by writing explicit terminators so each part announces its own end (null markers here). Length prefixes are the third common variant, and every real serialization format — JSON, protobuf, network protocols — picks one of these three. When you next design an encoding, ask the same question first: what tells the reader where this piece stops?
Object Persistence
Serialization & Deserialization Pipeline