362/670

362. Serialize and Deserialize BST

Medium

Design the two halves of a storage codec for a binary search tree:

serialize(root) receives the root of a BST (possibly empty) and returns a single string.
deserialize(data) receives that exact string and must reconstruct a tree identical to the original.

You choose the string format — the only contract is that the round trip deserialize(serialize(root)) rebuilds the same tree, which is what the judge checks by printing the rebuilt tree in level order. Node values are unique, as in any BST.

The design question hiding inside: a general binary tree needs null markers (or equivalent) to pin down its shape, but a BST's ordering property already encodes the shape. Aim for an encoding as compact as possible — can you get away with nothing but the values?

A BST and its null-free preorder encodingExample 1's BST. Because every value smaller than 5 must live in the left subtree and every larger one in the right, the preorder string "5 3 2 4 8 9" pins down the whole shape — no null markers required.

Example 1:

Input: deserialize(serialize(root)) where root = [5, 3, 8, 2, 4, null, 9]

Output: a tree identical to root

Explanation: The BST has root 5, left subtree {3: children 2 and 4}, and right subtree {8: right child 9}. Whatever string serialize emits, deserialize must rebuild this exact tree, so the judge prints back the same level order it read.

Example 2:

Input: deserialize(serialize(root)) where root = []

Output: an empty tree

Explanation: An empty tree must survive the round trip too — serialize may emit an empty string, and deserialize must map it back to no tree.

Constraints:

0 ≤ number of nodes ≤ 10⁴
0 ≤ node value ≤ 10⁴
All node values are unique, and the input tree is a valid BST.

Hints:

Any binary-tree codec works here: level order or preorder with explicit null markers round-trips every shape. Get that version passing first.

In a BST, a node's value tells you which side of every ancestor it belongs on. If you write the values in preorder, the first value is the root — which of the remaining values belong to its left subtree?

Rebuild from preorder with a (min, max) window: consume the next value only if it fits the current window, recursing left with (min, root) and right with (root, max). No null markers needed.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: root = [5, 3, 8, 2, 4, null, 9]

Expected output: [5, 3, 8, 2, 4, null, 9] (round trip preserved)