Serialize And Deserialize Binary Tree

Solution For Serialize And Deserialize Binary Tree

The problem of Serialize And Deserialize Binary Tree on leetcode is to design an algorithm to serialize and deserialize a 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. Deserialization is the reverse process, converting the bit sequence back into the original data structure.

To solve this problem, we can use a recursive approach.

  1. Serialization

In serialization, we need to traverse the binary tree and store its nodes in a string. We can use any traversal technique for this purpose. Here, we are using preorder traversal.

In preorder traversal, we first visit the root, then the left subtree, and then the right subtree. We can store the tree nodes in a string by appending the node values to the string with a delimiter.

Algorithm:
1. Create an empty string.
2. Traverse the tree recursively in preorder.
3. If the current node is null, append a ‘#’ character to the string and return.
4. Append the value of the current node followed by a delimiter to the string.
5. Recursively call the function for the left subtree and then the right subtree.

Code:

class Codec:
def serialize(self, root):
if not root:
return "#"
str_list = [] str_list.append(str(root.val))
str_list.append(self.serialize(root.left))
str_list.append(self.serialize(root.right))
return "|".join(str_list)

  1. Deserialization

In deserialization, we need to take the string we got from the serialization function and reconstruct the binary tree. We can use a similar recursive approach to do this.

Algorithm:
1. Split the string using the delimiter.
2. If the current element is ‘#’, return None.
3. Create a new node with the value of the current element.
4. Recursively call the function for the left subtree and then the right subtree.
5. Return the root node of the binary tree.

Code:

“`
class Codec:
def deserialize(self, data):
node_list = data.split(“|”)
root = self.buildTree(node_list)
return root

def buildTree(self, node_list):
    val = node_list.pop(0)
    if val == "#":
        return None
    node = TreeNode(int(val))
    node.left = self.buildTree(node_list)
    node.right = self.buildTree(node_list)
    return node

“`

To test the solution, we can create a binary tree, serialize it, and then deserialize it to get the original binary tree back.

Code:

“`

Creating a binary tree

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)

Creating an instance of Codec

codec = Codec()

Serializing the binary tree

serialized_tree = codec.serialize(root)
print(“Serialized tree:”, serialized_tree)

Deserializing the binary tree

deserialized_tree = codec.deserialize(serialized_tree)

Testing if the deserialized tree is same as the original tree

assert root.val == deserialized_tree.val
assert root.left.val == deserialized_tree.left.val
assert root.right.val == deserialized_tree.right.val
assert root.right.left.val == deserialized_tree.right.left.val
assert root.right.right.val == deserialized_tree.right.right.val
“`

Step by Step Implementation For Serialize And Deserialize Binary Tree

/**
 * 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) {
        
        // Base case
        if (root == null){
            return "";
        }
        
        // Recursive case
        StringBuilder sb = new StringBuilder();
        sb.append(root.val + ",");
        sb.append(serialize(root.left));
        sb.append(serialize(root.right));
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
        // Base case
        if (data == null || data.length() == 0){
            return null;
        }
        
        // Recursive case
        String[] vals = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty()){
            TreeNode curr = queue.poll();
            if (!vals[i].equals("")){
                curr.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(curr.left);
            }
            i++;
            if (!vals[i].equals("")){
                curr.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(curr.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
# Definition for a binary tree node.
# 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
        if not root:
            return "X"
        
        # preorder traversal
        left = self.serialize(root.left)
        right = self.serialize(root.right)
        
        return str(root.val) + "," + left + "," + right

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def dfs():
            val = next(vals)
            if val == "X":
                return None
            
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            
            return node
            
        # use a generator to iterate over data
        vals = iter(data.split(","))
        return dfs()

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

function serialize(root) {
    //Check for empty tree
    if(root === null) {
        return "";
    }
    //Create an array to store the tree nodes
    let arr = [];
    //Push the root node into the array
    arr.push(root);
    //Loop through the array while it's not empty
    while(arr.length) {
        //Get the first node in the array
        let node = arr.shift();
        //Check if the node is null
        if(node === null) {
            //If the node is null, add "null" to the array
            arr.push("null");
        } else {
            //If the node is not null, add the node's value to the array
            arr.push(node.val);
            //Push the node's left and right child into the array
            arr.push(node.left);
            arr.push(node.right);
        }
    }
    //Return the array as a string
    return arr.toString();
}

//Deserialize

function deserialize(data) {
    //Check for empty string
    if(data === "") {
        return null;
    }
    //Split the string into an array
    let arr = data.split(",");
    //Create a queue
    let queue = [];
    //Get the first value in the array (the root node)
    let root = new TreeNode(arr.shift());
    //Push the root node into the queue
    queue.push(root);
    //Loop through the array
    while(arr.length) {
        //Get the first node in the queue
        let node = queue.shift();
        //Get the next value in the array
        let val = arr.shift();
        //Check if the value is "null"
        if(val === "null") {
            //Do nothing
        } else {
            //Create a new node with the value
            let left = new TreeNode(val);
            //Set the node's left child to the new node
            node.left = left;
            //Push the new node into the queue
            queue.push(left);
        }
        //Get the next value in the array
        val = arr.shift();
        //Check if the value is "null"
        if(val === "null") {
            //Do nothing
        } else {
            //Create a new node with the value
            let right = new TreeNode(val);
            //Set the node's right child to the new node
            node.right = right;
            //Push the new node into the queue
            queue.push(right);
        }
    }
    //Return the root node
    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));
using System;
using System.Collections.Generic;

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) {
        // TODO: Implement this function
        return null;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        // TODO: Implement this function
        return null;
    }
}

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


Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]