Last updated on July 18th, 2024 at 10:43 pm

Here, We see Serialize and Deserialize BST LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Tree

Companies

Amazon

Level of Question

Medium

Serialize and Deserialize BST LeetCode Solution

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: []

1. Serialize and Deserialize BST LeetCode Solution 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);
    }
};

2. Serialize and Deserialize BST LeetCode Solution 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. Serialize and Deserialize BST Solution 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);
};

4. Serialize and Deserialize BST Solution 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'))