Serialize and Deserialize Binary Tree

HardBinary Trees

Design serialize and deserialize methods that turn a binary tree into a string and back.

Constraints

0 <= nodes <= 10^4
-1000 <= Node.val <= 1000

Preorder with null markers

Time O(n)Space O(n)

Serialize with a preorder walk writing values and a sentinel for null children. Deserialize by consuming tokens in the same preorder, rebuilding nodes recursively.

#include <bits/stdc++.h>
using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

class Codec {
public:
    string serialize(TreeNode* root) {
        string s;
        function<void(TreeNode*)> dfs = [&](TreeNode* node) {
            if (!node) { s += "# "; return; }
            s += to_string(node->val) + " ";
            dfs(node->left);
            dfs(node->right);
        };
        dfs(root);
        return s;
    }

    TreeNode* deserialize(string data) {
        istringstream in(data);
        function<TreeNode*()> build = [&]() -> TreeNode* {
            string tok;
            in >> tok;
            if (tok == "#") return nullptr;
            TreeNode* node = new TreeNode{stoi(tok), nullptr, nullptr};
            node->left = build();
            node->right = build();
            return node;
        };
        return build();
    }
};