serialize-deserialize.ts

import { TreeNode } from "../lib/tree-node.js";

/**
 * 297. Serialize and Deserialize Binary Tree  (Hard)
 * Link: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
 *
 * Design algorithms to serialize a binary tree to a string and deserialize that
 * string back to an identical tree.
 *
 * Example:
 *   serialize([1,2,3,null,null,4,5]) -> "1,2,#,#,3,4,#,#,5,#,#"
 *   deserialize(...) reconstructs the same tree.
 *
 * Approach:
 *   Pre-order DFS. serialize emits each node's value (or "#" for null) so the
 *   structure is fully captured. deserialize consumes the tokens in the same
 *   pre-order, recursively building left then right; a "#" yields a null child.
 *
 * Time:  O(n) for both directions.
 * Space: O(n)
 */
export function serialize(root: TreeNode | null): string {
  const tokens: string[] = [];

  function dfs(node: TreeNode | null): void {
    if (!node) {
      tokens.push("#");
      return;
    }
    tokens.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }

  dfs(root);
  return tokens.join(",");
}

export function deserialize(data: string): TreeNode | null {
  const tokens = data.split(",");
  let i = 0;

  function build(): TreeNode | null {
    const token = tokens[i++];
    if (token === "#") return null;
    const node = new TreeNode(Number(token));
    node.left = build();
    node.right = build();
    return node;
  }

  return build();
}