Serialize And Deserialize Binary Tree - Leetcode Solution

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)

2. 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

1