297. Serialize and Deserialize Binary Tree

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. 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.

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Solution

Approach 1: level order.

Approach 2: pre-order.

Code (Python)

Approach 1:

from collections import deque

NULL_NODE = '#'

class Codec:

    def serialize0(self, root):
        # level order
        queue = deque([root])
        vals = []
        while queue:
            node = queue.popleft()
            if not node:
                vals.append(NULL_NODE)
            else:
                vals.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        return ','.join(vals)
        

    def deserialize(self, data):
        # level order
        # a good place to use an iterator!
        vals = iter(data.split(','))
        root_val = next(vals)
        if root_val == NULL_NODE:
            return None
        root = TreeNode(int(root_val))
        queue = deque([root])
        while True:
            left_val, right_val = next(vals, None), next(vals, None) # provide a default value as an alternative to StopIteration error
            if not left_val or not right_val:
                return root
            parent = queue.popleft()
            parent.left = TreeNode(int(left_val)) if left_val != NULL_NODE else None
            parent.right = TreeNode(int(right_val)) if right_val != NULL_NODE else None
            for node in (parent.left, parent.right):
                if node:
                    queue.append(node)

Approach 2:

    def serialize(self, root):
        # preorder
        vals = []
        
        def recurse(node):
            if not node:
                vals.append(NULL_NODE)
                return
            vals.append(str(node.val))
            recurse(node.left)
            recurse(node.right)

        recurse(root)
        return ','.join(vals)
    
    def deserialize(self, data):
        # preorder
        vals = iter(data.split(','))
        
        def recurse():
            next_value = next(vals)
            if next_value == NULL_NODE:
                return None
            node = TreeNode(int(next_value))
            node.left = recurse() # won't exhaust the iterator because nodes are serialized the same way -- should be just right
            node.right = recurse()
            return node
        
        return recurse()

        '''
        #OR:
        splitted = data.split(',')
        
        def explore(index):
            # returns (node, index_to_consume_next)
            if index >= len(splitted) or splitted[index] == NULL_NODE:
                return (None, index + 1)
            root = TreeNode(int(splitted[index]))
            root.left, new_index = explore(index + 1)
            root.right, end_index = explore(new_index)
            return (root, end_index)
  
        return explore(0)[0]

        '''

Code (C++)

Approach 1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// Iteration - level by level.
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        queue<TreeNode*> q;
        if (root)
            q.push(root);
        ostringstream oss;
        while (!q.empty())
        {
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i)
            {
                TreeNode *node = q.front();
                q.pop();
                if (node)
                    oss << node->val << ",";
                else
                    oss << "null,";
                if (node)
                {
                    q.push(node->left);
                    q.push(node->right);
                }
            }
        }
        return oss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> q1;
        int head = 0;
        for (int tail = 0; tail < data.size(); ++tail)
        {
            if (data[tail] == ',')
            {
                q1.push(data.substr(head, tail-head));
                head = tail + 1;
            }
        }
        TreeNode *root = NULL;
        if (!q1.empty())
        {
            root = new TreeNode(stoi(q1.front()));
            q1.pop();
        }
        queue<TreeNode*> q2;
        q2.push(root);
        while (!q1.empty())
        {
            TreeNode *node = q2.front();
            q2.pop();
            // left child
            string left = q1.front();
            q1.pop();
            if (left != "null")
            {
                node->left = new TreeNode(stoi(left));
                q2.push(node->left);
            }
            // right child
            string right = q1.front();
            q1.pop();
            if (right != "null")
            {
                node->right = new TreeNode(stoi(right));
                q2.push(node->right);
            }
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

Approach 2:

// Recursion - preorder traversal.
class Codec {
private:
    TreeNode* doDeserialize(istringstream& iss) {
        string str;
        iss >> str;
        if (str == "N")
            return NULL;
        TreeNode *node = new TreeNode(stoi(str));
        node->left = doDeserialize(iss);
        node->right = doDeserialize(iss);
        return node;
    }
    
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL)
            return "N ";
        ostringstream oss;
        oss << root->val << ' '
            << serialize(root->left)
            << serialize(root->right);
        return oss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream iss(data);
        return doDeserialize(iss);
    }
};