Serialize and Deserialize Binary Tree

Share

Design an algorithm to serialize a binary tree to a string and deserialize the string back to the tree. No constraints on format.

Example 1
Input: root=[1,2,3,null,null,4,5] → serialize → "1,2,N,N,3,4,N,N,5,N,N" → deserialize → same tree

Solution Approach

Use preorder DFS. During serialization, output val for each node and "N" for nulls. During deserialization, split by comma and reconstruct using a queue.

  • Serialize: preorder DFS, append node.val or "N", separate by comma.
  • Deserialize: split string by comma into queue.
  • Recursive build: poll from queue; if "N" return null; else create node, recurse left, recurse right.
Java
import java.util.*;

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }
    private void dfs(TreeNode node, StringBuilder sb) {
        if (node == null) { sb.append("N,"); return; }
        sb.append(node.val).append(",");
        dfs(node.left, sb); dfs(node.right, sb);
    }
    public TreeNode deserialize(String data) {
        Deque<String> q = new ArrayDeque<>(Arrays.asList(data.split(",")));
        return build(q);
    }
    private TreeNode build(Deque<String> q) {
        String val = q.poll();
        if (val.equals("N")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = build(q); node.right = build(q);
        return node;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)