Solution For Serialize And Deserialize Bst

Problem:

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 search tree. There is no restriction on how you serialize/deserialize the binary search tree, you must ensure that it can be reconstructed.

The input data will only contain the root of the binary search tree.

Example 1:

Input: root = [2,1,3]

Output: [2,1,3]

Example 2:

Input: root = []

Output: []

Constraints:

The number of nodes in the tree is in the range [0, 104].

0 <= Node.val <= 104

The input data is guaranteed to be a valid binary search tree.

Solution:

Serialization is the process of converting an object into a format that can be easily stored or transmitted. In the case of a binary search tree, we can serialize it by traversing the tree – in this case, we will use pre-order traversal.

If a node is null, we will add a special marker (e.g. ‘#’) to indicate that it is null. Otherwise, we will add the node’s value to the serialization, then serialize its left and right subtrees recursively.

To deserialize the serialized tree, we can simply reverse the process. We start with the first value in the serialization and create a new node with that value. Then we recursively deserialize the left and right subtrees, using the special marker to indicate when a node is null.

Here is a detailed implementation of the solution in Python:

“””
Definition for a binary tree node.
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
“””

class Codec:
def serialize(self, root: TreeNode) -> str:
“””Encodes a tree to a single string.
“””
def traverse(node):
if not node:
return ‘#’
return str(node.val) + ‘,’ + traverse(node.left) + ‘,’ + traverse(node.right)

    return traverse(root)

def deserialize(self, data: str) -> TreeNode:
    """Decodes your encoded data to tree.
    """
    def build_tree(vals):
        if not vals:
            return None
        if vals[0] == '#':
            vals.pop(0)
            return None
        node = TreeNode(int(vals[0]))
        vals.pop(0)
        node.left = build_tree(vals)
        node.right = build_tree(vals)
        return node

    vals = data.split(',')
    return build_tree(vals)

Your Codec object will be instantiated and called as such:

ser = Codec()

deser = Codec()

ans = deser.deserialize(ser.serialize(root))

Step by Step Implementation For Serialize And Deserialize Bst

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }
    
    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        sb.append(node.val).append(",");
        buildString(node.left, sb);
        buildString(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        Queue nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(",")));
        return buildTree(nodes);
    }
    
    private TreeNode buildTree(Queue nodes) {
        String val = nodes.poll();
        if (val.equals("#")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(val));
        node.left = buildTree(nodes);
        node.right = buildTree(nodes);
        return node;
    }
}

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

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        # Base case: root is None
        if not root:
            return "None"
        
        # Recursive case: root is not None
        # Serialize left subtree
        left = self.serialize(root.left)
        
        # Serialize right subtree
        right = self.serialize(root.right)
        
        # Return string representation of current tree
        return str(root.val) + "," + left + "," + right

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        # Base case: data is "None"
        if data == "None":
            return None
        
        # Recursive case: data is not "None"
        # Split data into list of strings
        data_list = data.split(",")
        
        # Set root value to first element in list
        root = TreeNode(int(data_list[0]))
        
        # Set current node to root
        curr = root
        
        # Initialize stack
        stack = []
        
        # Initialize index
        i = 1
        
        # Iterate through list
        while i < len(data_list):
            
            # If current string is "None", set current node's left child to None and move to next string
            if data_list[i] == "None":
                curr.left = None
                i += 1
                
            # Else, current string is not "None"
            else:
                
                # If current node's left child is not None, push current node to stack and set current node to its left child
                if curr.left:
                    stack.append(curr)
                    curr = curr.left
                    
                # Else, current node's left child is None
                else:
                    
                    # Set current node's left child to a new TreeNode with value equal to current string
                    curr.left = TreeNode(int(data_list[i]))
                    
                    # Set current node to its left child
                    curr = curr.left
                    
                    # Move to next string
                    i += 1
                    
        # Set current node to root
        curr = root
        
        # Iterate through list
        while i < len(data_list):
            
            # If current string is "None", set current node's right child to None and move to next string
            if data_list[i] == "None":
                curr.right = None
                i += 1
                
            # Else, current string is not "None"
            else:
                
                # If current node is not None and current node's right child is None, set current node's right child to a new TreeNode with value equal to current string
                if curr and not curr.right:
                    curr.right = TreeNode(int(data_list[i]))
                    
                    # Set current node to its right child
                    curr = curr.right
                    
                    # Move to next string
                    i += 1
                    
                # Else, current node is None or current node's right child is not None
                else:
                    
                    # If stack is not empty, set current node to the node at the top of the stack and pop the stack
                    if stack:
                        curr = stack.pop()
                        
                    # Else, current node is None and stack is empty, so we have reached the end of the list
                    else:
                        break
        
        # Return root node
        return root

//Serialize: 

function serialize(root) { 
    if (!root) return []; 
    let vals = []; 
    function traverse(node) { 
        if (!node) return; 
        vals.push(node.val); 
        traverse(node.left); 
        traverse(node.right); 
    }
    traverse(root); 
    return vals; 
}

//Deserialize: 

function deserialize(data) { 
    if (!data.length) return null; 
    let root = new TreeNode(data[0]); 
    function buildTree(start, end) { 
        if (start > end) return null; 
        let mid = Math.floor((start + end) / 2); 
        let node = new TreeNode(data[mid]); 
        node.left = buildTree(start, mid - 1); 
        node.right = buildTree(mid + 1, end); 
        return node; 
    }
    buildTree(0, data.length - 1); 
    return root; 
}

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

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        
    }

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

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

public class TreeNode {
     public int val;
     public TreeNode left;
     public TreeNode right;
     public TreeNode(int x) { val = x; }
}
 
public class Codec {
 
    // Encodes a tree to a single string.
    public string serialize(TreeNode root) {
        // base case
        if (root == null) {
            return "";
        }
 
        // recursive case
        string leftSerialized = serialize(root.left);
        string rightSerialized = serialize(root.right);
 
        return root.val + "," + leftSerialized + "," + rightSerialized;
    }
 
    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        // base case
        if (data == "") {
            return null;
        }
 
        // recursive case
        string[] nodes = data.Split(',');
        int rootVal = int.Parse(nodes[0]);
 
        TreeNode root = new TreeNode(rootVal);
        root.left = deserialize(string.Join(",", nodes.Skip(1).Take(nodes.Length/2)));
        root.right = deserialize(string.Join(",", nodes.Skip(1 + nodes.Length/2).Take(nodes.Length/2)));
 
        return root;
    }
}