LeetCode 297: Serialize and Deserialize Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 297: Serialize and Deserialize Binary Tree?

In LeetCode 297: Serialize and Deserialize Binary Tree, you need to design a Codec class with two methods: serialize(root) to turn a binary tree into a string, and deserialize(data) to rebuild the tree from that string. A binary tree has nodes with a value, a left child, and a right child, and null nodes matter (e.g., [1,2,3,null,null,4,5]). For example, serialize [1,2,3] to a string like "1,2,3" and then rebuild it exactly. This problem tests your tree traversal and string skills, sharing a vibe with LeetCode 94: Binary Tree Inorder Traversal.

Problem Statement

• Input: A binary tree root for serialize; a string for deserialize.
• Output: A class with:
• serialize(root): Returns a string.
• deserialize(data): Returns the tree root.
• Rules: Rebuilt tree must match original; handle null nodes; any format as long as it works.

Constraints

• Tree nodes: 0 to 10⁴.
• Node values: -1000 to 1000.
• No duplicate values assumed.

Examples

• Input: root = [1,2,3,null,null,4,5]
• serialize(root) → "1,2,null,null,3,4,null,null,5,null,null"
• deserialize("1,2,null,null,3,4,null,null,5,null,null") → [1,2,3,null,null,4,5]
• Input: root = []
• serialize(root) → "null"
• deserialize("null") → []
• Input: root = [1]
• serialize(root) → "1,null,null"

Understanding the Problem: Packing and Unpacking a Tree

To solve LeetCode 297: Serialize and Deserialize Binary Tree in Python, we need to: 1. Turn a tree into a string that captures its structure—values and nulls. 2. Turn that string back into the same tree.

For [1,2,3], a string like "1,2,3" might lose nulls, so we need "null" markers (e.g., "1,2,null,null,3"). We’ll use:

• Best Solution (Preorder Traversal): O(n) time, O(n) space—fast and clear.
• Alternative Solution (Level-Order Traversal): O(n) time, O(n) space—visual but bulkier.

Let’s dive into the preorder solution with a friendly breakdown that’s easy to follow.

Best Solution: Preorder Traversal with String Manipulation

Why This Is the Best Solution

The preorder traversal approach is the top pick for LeetCode 297 because it’s efficient—O(n) time for both serialize and deserialize, O(n) space—and uses a natural tree traversal (root, left, right) that’s easy to rebuild. It packs the tree into a compact string with commas and "null" markers, making it straightforward to unpack. It’s like writing a travel log of the tree—root first, then branches—perfect for this task!

How It Works

Let’s picture this like packing a tree into a suitcase and unpacking it:

• Serialize (Packing):
• Start at the root, write its value.
• Go left, write its value (or "null" if empty), then right.
• Use commas to separate, like "1,2,null,null,3".
• Recurse down the tree, preorder style.
• Deserialize (Unpacking):
• Split the string into a list (e.g., ["1", "2", "null", "null", "3"]).
• Use a pointer to track your spot in the list.
• Build the tree: root first, then left, then right, skipping "null".
• Why It Works:
• Preorder ensures root comes before children, matching build order.
• "null" markers preserve structure, avoiding ambiguity.

It’s like a tree diary—write it down, then rebuild it step-by-step!

Step-by-Step Example

Example: root = [1,2,3,null,null,4,5]

• Serialize:
• Root: 1 → "1".
• Left: 2 → "1,2".
• Left: null → "1,2,null".
• Right: null → "1,2,null,null".
• Right: 3 → "1,2,null,null,3".
• Left: 4 → "1,2,null,null,3,4".
• Left: null → "1,2,null,null,3,4,null".
• Right: null → "1,2,null,null,3,4,null,null".
• Right: 5 → "1,2,null,null,3,4,null,null,5".
• Left: null → "1,2,null,null,3,4,null,null,5,null".
• Right: null → "1,2,null,null,3,4,null,null,5,null,null".
• Result: "1,2,null,null,3,4,null,null,5,null,null".
• Deserialize:
• Split: ["1", "2", "null", "null", "3", "4", "null", "null", "5", "null", "null"].
• idx=0: Root = 1.
• idx=1: Left = 2.
• idx=2: Left = null, idx=3: Right = null.
• idx=4: Right = 3.
• idx=5: Left = 4.
• idx=6: Left = null, idx=7: Right = null.
• idx=8: Right = 5.
• idx=9: Left = null, idx=10: Right = null.
• Result: [1,2,3,null,null,4,5].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy code# 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):
        # Step 1: Pack the tree into a string
        if not root:  # Empty node
            return "null"
        # Preorder: root, left, right
        return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}"

    def deserialize(self, data):
        # Step 2: Unpack the string into a tree
        def dfs():
            val = next(vals)  # Get next value from iterator
            if val == "null":  # Empty node
                return None
            node = TreeNode(int(val))  # Make new node
            node.left = dfs()  # Build left subtree
            node.right = dfs()  # Build right subtree
            return node

        vals = iter(data.split(","))  # Split string into iterator
        return dfs()  # Start rebuilding

• Serialize:
• Line 11-12: If root is None, return "null".
• Line 14: Format as "val,left,right" using recursion—e.g., "1,2,null,null".
• Deserialize:
• Line 17-24: Helper dfs:
• Line 19: Grab next value from iterator.
• Line 20-21: If "null", return None.
• Line 22-24: Create node, recurse for left and right, return node.
• Line 26: Split string into list, make iterator.
• Line 27: Start rebuilding with dfs.

• Time Complexity: O(n) for both—visits each node once.
• Space Complexity: O(n)—string and recursion stack.

This is like a tree postcard—write it, send it, rebuild it!

Alternative Solution: Level-Order Traversal

Why an Alternative Approach?

Level-order traversal (BFS) uses a queue to serialize and deserialize—O(n) time, O(n) space. It’s more visual, listing nodes level by level (e.g., "1,2,3,null,null,4,5"), but the string can be bulkier with more "null"s. It’s like drawing a tree layer-by-layer—clear but less compact.

How It Works

Let’s think of this as layering the tree:

• Serialize: Use a queue to visit level-by-level, adding "null" for empty children.
• Deserialize: Build level-by-level, pairing children with parents from the string.

It’s like stacking the tree floor-by-floor!

Step-by-Step Example

Example: root = [1,2,3,null,null,4,5]

• Serialize:
• Queue: [1] → "1", add 2,3 → "1,2,3".
• Queue: [2,3] → "1,2,3,null,null,4,5".
• Result: "1,2,3,null,null,4,5".
• Deserialize:
• List: ["1", "2", "3", "null", "null", "4", "5"].
• Root = 1, queue = [1].
• 1’s kids: 2, 3 → queue = [2, 3].
• 2’s kids: null, null.
• 3’s kids: 4, 5.
• Result: [1,2,3,null,null,4,5].

Code for Level-Order Approach

Copy codeclass Codec:
    def serialize(self, root):
        if not root:
            return "null"
        result = []
        queue = [root]
        while queue:
            node = queue.pop(0)
            result.append(str(node.val) if node else "null")
            if node:
                queue.append(node.left)
                queue.append(node.right)
        return ",".join(result)

    def deserialize(self, data):
        if data == "null":
            return None
        vals = data.split(",")
        root = TreeNode(int(vals[0]))
        queue = [root]
        i = 1
        while queue and i < len(vals):
            node = queue.pop(0)
            if i < len(vals) and vals[i] != "null":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if i < len(vals) and vals[i] != "null":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root

• Time Complexity: O(n)—visits each node.
• Space Complexity: O(n)—queue and string.

It’s a layer-by-layer build!

Comparing the Two Solutions

• Preorder (Best):
• Pros: O(n) time, O(n) space, compact string.
• Cons: Recursive depth.
• Level-Order (Alternative):
• Pros: O(n) time, O(n) space, visual structure.
• Cons: Bulkier string, more "null"s.

Preorder wins for efficiency.

Additional Examples and Edge Cases

• []: "null".
• [1,2]: "1,2,null,null".
• [1,null,2]: "1,null,2,null,null".

Both work, preorder’s leaner.

Complexity Breakdown

• Preorder: Time O(n), Space O(n).
• Level-Order: Time O(n), Space O(n).

Preorder’s the champ.

Key Takeaways

• Preorder: Root-first—sleek!
• Level-Order: Layer-by-layer—clear!
• Trees: Strings can rebuild them.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Tree on a String

LeetCode 297: Serialize and Deserialize Binary Tree in Python is a cool tree challenge. Preorder keeps it tight, while level-order paints the picture. Want more? Try LeetCode 94: Binary Tree Inorder Traversal or LeetCode 449: Serialize and Deserialize BST. Ready to pack? Head to Solve LeetCode 297 on LeetCode and string that tree today!