Jake Tuero

Serialize and Deserialize Binary Tree

3 min read

Serialize and Deserialize Binary Tree

Problem

Implement an algorithm to serialize and deserialize a binary tree.

Serialization is the process of converting an in-memory structure into a sequence of bits so that it can be stored or sent across a network to be reconstructed later in another computer environment.

You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. There is no additional restriction on how your serialization/deserialization algorithm should work.

Note: The input/output format in the examples is the same as how NeetCode serializes a binary tree. You do not necessarily need to follow this format.

Examples

Example 1:

Input: root = [1,2,3,null,null,4,5]

Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []

Output: []

Constraints

  • 0 <= The number of nodes in the tree <= 1000.
  • -1000 <= Node.val <= 1000

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

Solution

We serialize in preorder (root, left subtree, right subtree), with a special token for nullptr. This allows us to do preorder, as we have the nullptrs in the string. If we didn’t have this, we would need something like both preorder and inorder.

To deserialize, we index linearly through the input while running DFS (preorder). If the next char is the special token, we increment and return nullptr (this is a leaf). Otherwise, we read token and increment index, create our local root, set the left and right subtrees through recursion, then return the local root.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
class Codec {
public:
 
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        std::stringstream ss;
 
        // Serialize in preorder
        std::function<void(TreeNode*)> runner;
        runner = [&](TreeNode* node) {
            // Special tag for nullptr
            if (!node) {
                ss << "N,";
                return;
            }
            ss << std::to_string(node->val) << ",";
            runner(node->left);
            runner(node->right);
        };
        runner(root);
        auto s = std::move(ss).str();
        s.pop_back();
        return s;
    }
 
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        std::vector<std::string> tokens;
        std::string token;
        std::stringstream ss(data);
        // Read tokens separated by a comma delimiter
        while (std::getline(ss, token, ',')) {
            tokens.push_back(token);
        }
 
        std::size_t idx = 0;
        std::function<TreeNode*()> runner;
        runner = [&]() -> TreeNode* {
            // If we read a N, no substree so early break 
            if (tokens[idx] == "N") { ++idx; return nullptr; } 
            TreeNode *node = new TreeNode(stoi(tokens[idx++]));
            node->left = runner();
            node->right = runner();
            return node;
        };
        return runner();
    }
};

Graph View