Leetcode 449. Serialize and Deserialize BST

Problem Explanation:

The problem is asking to convert a binary search tree into a serialized string form that can be later converted back into a binary search tree. This process needs to have the original tree structure preserved.

For example, Consider the following binary tree

1
2
3    2
4   / \
5  1   3

The serialized string can be "2 1 3" which can be later deserialized back to the original binary tree.

Approach:

The solution to this problem involves a simple Depth-First-Search (DFS) traversal for both the serialization and deserialization process.

1. Serialization: The idea is to start from the root, and perform a pre-order traversal. For this, the current node's value is added to the resulting string. As we traverse, we add a space after each node to separate the node values. Once the traversal is done, we have a serialized string of the BST.

2. Deserialization: We start by splitting the serialized string into node values. For each node value, we compare it with the minimum and maximum value of the subtree (at the start, the minimum is INT_MIN and maximum is INT_MAX). If it falls in the range, we create a new node with that value and then recursively do the same for left and right subtree. If it doesn't fall in the range, we simply return NULL.

Python Solution:

1
2python
3import sys
4import collections
5
6class Solution:
7    def serialize(self, root):
8        def dfs(node):
9            if node:
10                vals.append(str(node.val))
11                dfs(node.left)
12                dfs(node.right)
13        vals = []
14        dfs(root)
15        return ' '.join(vals)
16
17    def deserialize(self, data):
18        def helper(lower = -sys.maxsize, upper = sys.maxsize):
19            if not vals or vals[0] < lower or vals[0] > upper:
20                return None
21
22            val = vals.popleft()
23            node = TreeNode(val)
24            node.left = helper(lower, val)
25            node.right = helper(val, upper)
26            return node
27
28        vals = collections.deque(int(val) for val in data.split())
29        return helper()

Java Solution:

1
2java
3public class Codec {
4
5    public String serialize(TreeNode root) {
6        StringBuilder sb = new StringBuilder();
7        serialize(root, sb);
8        return sb.toString();
9    }
10
11    private void serialize(TreeNode root, StringBuilder sb) {
12        if (root == null) {
13            return;
14        }
15        sb.append(root.val).append(" ");
16        serialize(root.left, sb);
17        serialize(root.right, sb);
18    }
19
20    public TreeNode deserialize(String data) {
21        if (data.isEmpty()) {
22            return null;
23        }
24        Queue<String> nodesRemaining = new LinkedList<>(Arrays.asList(data.split(" ")));
25        return deserialize(nodesRemaining, Integer.MIN_VALUE, Integer.MAX_VALUE);
26    }
27
28    private TreeNode deserialize(Queue<String> nodesRemaining, int lower, int upper) {
29        if (nodesRemaining.isEmpty()) {
30            return null;
31        }
32        int val = Integer.parseInt(nodesRemaining.peek());
33        if (val < lower || val > upper) {
34            return null;
35        }
36        nodesRemaining.poll();
37        TreeNode root = new TreeNode(val);
38        root.left = deserialize(nodesRemaining, lower, val);
39        root.right = deserialize(nodesRemaining, val, upper);
40        return root;
41    }
42}

Javascript Solution:

1
2javascript
3var serialize = function(root) {
4    const data = [];
5    preOrder(root, data);
6    return data.join(' ');
7  };
8  
9  var preOrder = function(node, data) {
10    if (!node) return;
11    data.push(node.val);
12    preOrder(node.left, data);
13    preOrder(node.right, data);      
14  }
15  
16var deserialize = function(data) {
17    if (!data.length)  return null;
18    data = data.split(' ').map(n => Number(n));
19
20    return buildBST(data, -Infinity, Infinity);
21  };
22
23var buildBST = function(data, min, max) {
24    if (data[0] < min || data[0] > max) return null;
25    let val = data.shift();
26    let node = new TreeNode(val);
27    node.left = buildBST(data, min, val);
28    node.right = buildBST(data, val, max);        
29    return node;
30}

C++ Solution:

1
2c++
3class Codec {
4public:
5
6    string serialize(TreeNode* root) {
7        stringstream out;
8        serialize(root, out);
9        return out.str();
10    }
11
12    TreeNode* deserialize(string data) {
13        stringstream in(data);
14        return deserialize(in, INT_MIN, INT_MAX);
15    }
16
17private:
18
19    void serialize(TreeNode* root, stringstream& out) {
20        if (root) {
21            out << root->val << ' ';
22            serialize(root->left, out);
23            serialize(root->right, out);
24        }
25    }
26
27    TreeNode* deserialize(stringstream& in, long min, long max) {
28        string val;
29        in>>val;
30        long num = stol(val);
31
32        if(val == ""|| num  min || num > max ) return NULL;
33
34        TreeNode* root = new TreeNode(num);
35        root->left = deserialize(in, min, num);
36        root->right = deserialize(in, num, max);
37        return root;
38    }
39};

In the above Python solution, the dfs function is used to traverse through the binary tree and serialize it. Initially, the vals list is created to hold node values. Then the dfs function is called with the root node to start traversing the BST.

The helper function is used in the deserialization process. It takes two arguments, lower and upper. These two arguments represent the range for the current subtree. Initially, they are set to INT_MIN and INT_MAX. Inside the function, the function checks whether there are any values left in the vals deque or whether the first value in the deque is out of the range. If either of these conditions is true the function returns None indicating the end of this subtree. Otherwise, it creates a TreeNode with the first value in vals and recursively calls itself for creating left and right subtrees.

In the Java and Javascript solutions, the approach is similar to Python but uses different language constructs. A StringBuilder is used in Java to append the serialized string, and in Javascript, an array is used. The deserialize method of Java and Javascript returns a TreeNode as well and hence the approach remains the same.

In the C++ solution, we used a function serialize to print the preorder traversal of the given tree. And for deserialize function, it parse a value and then it will recursively descend the tree. It checks if the current value is within the range specified by the current subtree (min, max). If it is, it creates a new node with this value and recursively fills its left and right subtrees. If it isn't, it returns NULL. A distinct feature in this solution is that stringstream is used while serializing and deserializing.

All solutions have their time complexity as O(n), where n is the number of nodes because we are visiting every node exactly once. The space complexity is also O(n) as we are using additional space to store the serialized string, where n is the number of nodes in the tree.