Serialize and deserialize a binary tree

Write the tree in preorder with # for every missing child, then rebuild it by reading the tokens back in the same order.

The idea

Preorder writes a node before its subtrees, so the reader always learns a node before it needs to attach children to it. Values alone are ambiguous (1, 2 could be 2 as a left or a right child), so write # wherever a child is missing. Then reading is the same recursion: take the next token; # means null, anything else becomes a node whose left subtree, then right subtree, are read from the tokens that follow.

Code

public class Codec {
    public string serialize(TreeNode root) {
        var parts = new List<string>();
        Write(root, parts);
        return string.Join(",", parts);
    }
    private void Write(TreeNode node, List<string> parts) {
        if (node == null) { parts.Add("#"); return; }
        parts.Add(node.val.ToString());
        Write(node.left, parts);
        Write(node.right, parts);
    }

    public TreeNode deserialize(string data) {
        var tokens = new Queue<string>(data.Split(','));
        return Read(tokens);
    }
    private TreeNode Read(Queue<string> tokens) {
        string t = tokens.Dequeue();
        if (t == "#") return null;
        var node = new TreeNode(int.Parse(t));
        node.left = Read(tokens);
        node.right = Read(tokens);
        return node;
    }
}

Tips

• A tree with n nodes writes exactly n values and n + 1 # markers.
• The reader never needs lengths or brackets: the # markers tell it exactly where each subtree ends.
• Level order with null markers (the LeetCode input format) works too; it uses a queue on both sides instead of recursion.

In the .NET library

Use a StringBuilder or List<string> plus string.Join rather than += in a loop, which copies the whole string each time. For real persistence, System.Text.Json can serialize a TreeNode class directly, but deep trees then hit its MaxDepth limit (64 by default).