deepSWE.io

Serialize and Deserialize Binary Tree

TreeDFSDesign

25 min

Problem Statement

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

Example

Example 1:

Serialized: "1,2,null,null,3,4,null,null,5,null,null"

Solution (DFS with Pre-order Traversal)

The solution uses a Depth-First Search (DFS) with pre-order traversal to serialize the tree into a string. The same traversal order is used to deserialize the string back into a tree.

Algorithm Steps

Serialization:
- Use a pre-order traversal (root, left, right).
- If a node is null, append a special marker (e.g., "null") to the string.
- Otherwise, append the node's value and continue the traversal.
Deserialization:
- Split the serialized string into a list of values.
- Use a queue to process the values in order.
- If a value is the special marker, return null.
- Otherwise, create a new node with the value and recursively build the left and right subtrees.

Start: Serialize the tree to a string.

Result:

Serialize and Deserialize Binary Tree Solution


# 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
        """
        res = []
        
        def dfs(node):
            if not node:
                res.append("N")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        
        dfs(root)
        return ",".join(res)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        vals = data.split(',')
        self.i = 0
        
        def dfs():
            if vals[self.i] == "N":
                self.i += 1
                return None
            
            node = TreeNode(int(vals[self.i]))
            self.i += 1
            node.left = dfs()
            node.right = dfs()
            return node
            
        return dfs()

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))