Serialize and Deserialize Binary Tree
Problem Statement
Implement an algorithm to serialize and deserialize a binary tree.
Serialization is the process of converting an in-memory structure into a sequence of bits so that it can be stored or sent across a network to be reconstructed later in another computer environment.
You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. There is no additional restriction on how your serialization/deserialization algorithm should work.
Note: The input/output format in the examples is just one way to serialize a binary tree. You do not necessarily need to follow this format.
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = []
Output: []
Constraints:
0 <= The number of nodes in the tree <= 1000
.-1000 <= Node.val <= 1000
You should aim for a solution with O(n)
time and O(n)
space, where n
is the number of nodes in the given tree.
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(n)
space, where n
is the number of nodes in the given tree.
Hint 1
A straightforward way to serialize a tree is by traversing it and adding nodes to a string separated by a delimiter (example: ā,ā), but this does not handle null
nodes effectively. During deserialization, it becomes unclear where to stop or how to handle missing children. Can you think of a way to indicate null
nodes explicitly?
Hint 2
Including a placeholder for null
nodes (example: āNā) during serialization ensures that the exact structure of the tree is preserved. This placeholder allows us to identify missing children and reconstruct the tree accurately during deserialization.
Hint 3
We can use the Depth First Search (DFS) algorithm for both serialization and deserialization. During serialization, we traverse the tree and add node values to the result string separated by a delimiter, inserting N
whenever we encounter a null
node. During deserialization, we process the serialized string using an index i
, create nodes for valid values, and return from the current path whenever we encounter N
, reconstructing the tree accurately.
Solution
Depth First Search
# 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
def serialize(root: Optional[TreeNode]) -> 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(data: str) -> Optional[TreeNode]: vals = data.split(",") i = 0
def dfs(): nonlocal i if vals[i] == "N": i += 1 return None node = TreeNode(int(vals[i])) i += 1 node.left = dfs() node.right = dfs() return node
return dfs()
Time complexity: O(n)
Space complexity: O(n)