We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Serialize and Deserialize Binary Tree

Difficulty: Hard

Problem Description

Design an algorithm to serialize and deserialize a binary tree. The serialization process converts the binary tree into a string format, while deserialization reconstructs the original tree structure from that string.

Key Insights

  • Serialization converts a binary tree into a string representation.
  • Deserialization reconstructs the binary tree from its string representation.
  • Handling null values is crucial to accurately represent the tree structure.
  • Depth-First Search (DFS) or Breadth-First Search (BFS) can be used for traversal during serialization and deserialization.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree, since each node is processed once during serialization and deserialization. Space Complexity: O(N), for the storage of the serialized string and the recursion stack during the tree traversal.

Solution

The solution uses Depth-First Search (DFS) to traverse the binary tree. During serialization, we perform a pre-order traversal of the tree, appending values to a string, and using a special marker (e.g., "null") for null nodes. For deserialization, we split the string back into values and reconstruct the tree recursively by reading values in pre-order.

Code Solutions

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):
        """Encodes a tree to a single string."""
        def dfs(node):
            if not node:
                return "null,"
            return str(node.val) + "," + dfs(node.left) + dfs(node.right)
        return dfs(root)

    def deserialize(self, data):
        """Decodes your encoded data to tree."""
        def dfs(nodes):
            val = next(nodes)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = dfs(nodes)
            node.right = dfs(nodes)
            return node
        return dfs(iter(data.split(',')))

# Example usage:
# codec = Codec()
# tree_string = codec.serialize(root)
# root = codec.deserialize(tree_string)
← Back to All Questions