Serialize and Deserialize Binary Tree

hard tree dfs design

Problem

Design two functions: one that turns a binary tree into a string and another that reconstructs the tree from that string. Use preorder traversal with a sentinel for null children.

Inputtree = 1,2,null,null,3,4,null,null,5,null,null (preorder)

Outputsame tree

Serialize: preorder DFS, emit "#" for null. Deserialize: read tokens in order, recursively build.

tree (level order, 'null' for missing)

def serialize(root):
    parts = []
    def go(n):
        if not n:
            parts.append("#")
            return
        parts.append(str(n.val))
        go(n.left)
        go(n.right)
    go(root)
    return ",".join(parts)

def deserialize(s):
    tokens = iter(s.split(","))
    def build():
        t = next(tokens)
        if t == "#":
            return None
        n = TreeNode(int(t))
        n.left = build()
        n.right = build()
        return n
    return build()

function serialize(root) {
  const parts = [];
  (function go(n) {
    if (!n) { parts.push("#"); return; }
    parts.push(String(n.val));
    go(n.left); go(n.right);
  })(root);
  return parts.join(",");
}

function deserialize(s) {
  const tokens = s.split(",");
  let i = 0;
  function build() {
    const t = tokens[i++];
    if (t === "#") return null;
    return { val: Number(t), left: build(), right: build() };
  }
  return build();
}

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    go(root, sb);
    return sb.toString();
}
private void go(TreeNode n, StringBuilder sb) {
    if (n == null) { sb.append("#,"); return; }
    sb.append(n.val).append(",");
    go(n.left, sb); go(n.right, sb);
}
public TreeNode deserialize(String s) {
    Deque<String> q = new ArrayDeque<>(Arrays.asList(s.split(",")));
    return build(q);
}
private TreeNode build(Deque<String> q) {
    String t = q.poll();
    if (t.equals("#")) return null;
    TreeNode n = new TreeNode(Integer.parseInt(t));
    n.left = build(q); n.right = build(q);
    return n;
}

void go(TreeNode* n, string& s) {
    if (!n) { s += "#,"; return; }
    s += to_string(n->val) + ",";
    go(n->left, s); go(n->right, s);
}
string serialize(TreeNode* root) { string s; go(root, s); return s; }

TreeNode* build(istringstream& in) {
    string t; getline(in, t, ',');
    if (t == "#") return nullptr;
    auto* n = new TreeNode(stoi(t));
    n->left = build(in); n->right = build(in);
    return n;
}
TreeNode* deserialize(string s) { istringstream in(s); return build(in); }

Time: O(n) Space: O(n)