Last updated on January 5th, 2025 at 11:59 pm

Here, we see a Serialize and Deserialize BST LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Tree

Companies

Amazon

Level of Question

Medium

Serialize and Deserialize BST LeetCode Solution

1. Problem Statement

Serialization is 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:
Input: root = [2,1,3]
Output: [2,1,3]

Example 2:
Input: root = []
Output: []

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Tree Depth First Search (DFS). The serialization and deserialization processes rely on recursive traversal of the binary tree, which is a classic DFS approach. Specifically:

• Serialization: Preorder traversal (root → left → right) is used to convert the tree into a string representation.
• Deserialization: The string is processed recursively to reconstruct the tree using preorder traversal constraints.

3. Code Implementation in Different Languages

3.1 Serialize and Deserialize BST C++

class Codec {
public:
    void serializehelper(TreeNode* root, string& s){
        if(root==nullptr) return;
        s+=to_string(root->val) + ",";
        serializehelper(root->left, s);
        serializehelper(root->right, s);
    }
    string serialize(TreeNode* root) {
        if(root==nullptr) return "";
        string s="";
        serializehelper(root, s);
        return s;
    }
    int convertStringtoInt(string& data, int& pos){
        pos=data.find(',');
        int value=stoi(data.substr(0, pos));
        return value;
    }
    
    TreeNode* deserializehelper(string& data, int min, int max) {
        if(data.size()==0) return nullptr;
        int pos=0;
        int value = convertStringtoInt(data, pos);
        if (value < min || value > max) return nullptr;
        TreeNode* tnode = new TreeNode(value); 
        data=data.substr(pos+1);
        tnode->left=deserializehelper(data, min, tnode->val);
        tnode->right=deserializehelper(data, tnode->val, max);
        return tnode;
    }
    
    TreeNode* deserialize(string data) {
        if(data=="") return nullptr;
        return deserializehelper(data, INT_MIN, INT_MAX);
    }
};

3.2 Serialize and Deserialize BST Java

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder res = new StringBuilder();
        helpserialize(root,res);
        return res.toString();
    }

    private void helpserialize(TreeNode root, StringBuilder res){
        if(root == null){
            res.append("x,");
            return ;
        }
        res.append(root.val);
        res.append(',');
        helpserialize(root.left, res);
        helpserialize(root.right, res);
    }

    public TreeNode deserialize(String data) {
        Deque<String> q = new LinkedList<>();
        q.addAll(Arrays.asList(data.split(",")));
        return helpdeserialize(q);
    }

    private TreeNode helpdeserialize(Deque<String> q){
        String res = q.remove();
        if(res.equals("x")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(res));
        root.left = helpdeserialize(q);
        root.right = helpdeserialize(q);
        return root;
    }
}

3.3 Serialize and Deserialize BST JavaScript

var serialize = function(root) {
    let preorder = [];
    let dfs = function(node) {
        if (node==null) return;
        preorder.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }
    dfs(root);
    return preorder.join(',');
};

 var deserialize = function(data) {
    if (data == '') return null;
    let preorder = data.split(',');
    let recur = function(lower, upper) {
        if (Number(preorder[0]) < lower || Number(preorder[0]) > upper) return null;
        if (preorder.length == 0) return null;
        let root = new TreeNode(preorder.shift());
        root.left = recur(lower, root.val);
        root.right = recur(root.val, upper);
        return root;
    }
    return recur(-Infinity, Infinity);
};

3.4 Serialize and Deserialize BST Python

class Codec:
    def serialize(self, root):
        path_of_preorder = []
        def helper( node ):
            if node:
                path_of_preorder.append( node.val )
                helper( node.left )
                helper( node.right )
        helper( root )
        return '#'.join( map(str, path_of_preorder) )
        
    def deserialize(self, data):
        if not data:
            return None
        node_values = deque(  int(value) for value in data.split('#') )
        def helper( lower_bound, upper_bound):
            if node_values and lower_bound < node_values[0] < upper_bound:
                root_value = node_values.popleft()
                root_node = TreeNode( root_value )
                root_node.left = helper( lower_bound, root_value )
                root_node.right = helper( root_value, upper_bound )
                return root_node
        return helper( float('-inf'), float('inf'))    

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(n)
Java	O(n)	O(n)
JavaScript	O(n)	O(n)
Python	O(n)	O(n)