LeetCode Solutions Blog

Serialize and Deserialize Binary Tree

Number: 297

Difficulty: Hard

Paid? No

Problem Description

Design an algorithm to serialize and deserialize a binary tree. Serialization converts a binary tree structure into a string, while deserialization reconstructs the original tree from the string. There is no specific format required, so you can choose any method that accurately preserves the tree structure.

Key Insights

The tree can be traversed using either depth-first search (DFS) or breadth-first search (BFS).
Using BFS (level-order traversal) simplifies reconstruction since nodes are processed level-by-level.
Placeholder markers (e.g., "null") are used to indicate missing children.
Both serialization and deserialization processes should handle empty trees and edge cases gracefully.
Ensuring a one-to-one mapping between the tree structure and the serialized string is critical.

Space and Time Complexity

Time Complexity: O(n) for both serialization and deserialization, where n is the number of nodes in the tree. Space Complexity: O(n) due to the storage used for the serialized string and additional data structures (queue) during processing.

Solution

This solution uses level-order traversal (BFS) for both serialization and deserialization. During serialization, each node is processed sequentially with missing children recorded as "null". For deserialization, the string is split by commas, and a queue is used to rebuild the tree level by level. The root is created from the first token, then subsequent tokens are assigned as left and right children accordingly, ensuring an accurate reconstruction of the original tree.

Code Solutions

Below are example implementations in Python, JavaScript, C++, and Java with detailed comments.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val        # value of the node
        self.left = left      # left child
        self.right = right    # right child

class Codec:
    # Encodes a tree to a single string using BFS.
    def serialize(self, root):
        if not root:
            return ""  # Return empty string for an empty tree
        result = []
        queue = [root]  # Initialize the queue with the root node
        while queue:
            node = queue.pop(0)
            if node:
                result.append(str(node.val))  # Append the value of the node
                queue.append(node.left)         # Enqueue left child
                queue.append(node.right)        # Enqueue right child
            else:
                result.append("null")           # Placeholder for null node
        return ",".join(result)  # Join list with commas to form the string
    
    # Decodes the encoded data to reconstruct the tree using BFS.
    def deserialize(self, data):
        if not data:
            return None  # Return None for empty string
        nodes = data.split(",")
        root = TreeNode(int(nodes[0]))  # Create root node from first element
        queue = [root]
        i = 1  # Index for traversing nodes list
        while queue:
            current = queue.pop(0)
            if i < len(nodes) and nodes[i] != "null":
                current.left = TreeNode(int(nodes[i]))
                queue.append(current.left)
            i += 1
            if i < len(nodes) and nodes[i] != "null":
                current.right = TreeNode(int(nodes[i]))
                queue.append(current.right)
            i += 1
        return root