Serialize and Deserialize Binary Tree

hard tree dfs design

Problem

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work.

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); }

Explanation

To turn a tree into a string and back, we use a preorder DFS (node, then left, then right) and — crucially — write a placeholder "#" for every null child. Recording the nulls is what makes the shape recoverable later.

To serialize, we visit nodes in preorder, appending each value, and appending "#" whenever we hit an empty spot. Joining the pieces with commas gives one flat string like 1,2,#,#,3,....

To deserialize, we read the tokens left to right with a moving index. The build function takes the next token: if it's "#" it returns null; otherwise it makes a node and then recursively builds its left child and right child — in the exact same order the tokens were written.

Example: tree with root 1, left 2, right 3. Serialize emits 1, 2, #, #, 3, #, #. Rebuilding reads 1, then builds left from 2 (whose two children are #, #), then builds right from 3 the same way — reproducing the original tree.

Because encoding and decoding walk the nodes in the identical preorder sequence, the reconstruction lines up perfectly, and both passes run in linear time.

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