Binary Tree Serialization and Deserialization

Implement two functions, serialize and deserialize, that together let you turn an in-memory binary tree into a string and rebuild the same tree back from that string. This is LeetCode 297 — the classic "send a tree over the wire" problem. The pair is a closed loop: the exact string format is yours to design, but deserialize(serialize(t)) must produce a tree with the same shape and the same values as t.

A node is the plain object { value, left, right } with left and right either pointing at another node or being null. The tree is not a search tree — values can repeat, and there is no left-smaller / right-larger rule.

Signature

type TreeNode = { value: number; left: TreeNode | null; right: TreeNode | null } | null;

function serialize(root: TreeNode): string;
function deserialize(str: string): TreeNode;

Examples

// Empty tree
serialize(null);                 // any string you like — the convention here is "#"
deserialize(serialize(null));    // null

// Single node
const t = { value: 7, left: null, right: null };
deserialize(serialize(t));       // { value: 7, left: null, right: null }

// Balanced three-node tree
//        1
//       / \
//      2   3
const t = {
  value: 1,
  left:  { value: 2, left: null, right: null },
  right: { value: 3, left: null, right: null },
};
deserialize(serialize(t));       // structurally equal to t

// Skewed tree — only a left child at every level
//   1
//  /
// 2
//  \
//   3
const t = {
  value: 1,
  left: {
    value: 2,
    left: null,
    right: { value: 3, left: null, right: null },
  },
  right: null,
};
deserialize(serialize(t));       // structurally equal to t — null markers
                                 // are what tell left from right

Notes

• Round-trip is the contract. deserialize(serialize(t)) must equal t by deep structural comparison. The actual string format is an implementation detail — pick one that makes both directions cheap.
• Null subtrees count. A tree with only a left child must serialize differently from a tree with only a right child. If your format can't tell those apart, it's wrong.
• Values are numbers. Treat the value field as a finite number (including 0, negatives, and floats). String values, NaN, and Infinity are out of scope — pick a delimiter your numbers can't contain.
• serialize does not mutate. Reading the tree to produce a string must leave the input tree's nodes and pointers exactly as they were.
• Determinism in both directions. The same tree must always produce the same string. The same valid string must always produce a structurally equal tree.
• Malformed input. Calling deserialize on garbage (extra tokens, missing tokens, junk values) may behave however you choose — but document your choice in a comment and keep it consistent across the suite.