Serialize and Deserialize Binary Tree in DSA Python

Mental Model

We turn a tree into a string to save or send it, then rebuild the exact same tree from that string.

Analogy: Like writing a family tree on paper with names and empty spots, then using that paper to redraw the family tree exactly as it was.

    1
   / \
  2   3
     / \
    4   5

Dry Run Walkthrough

Input: Tree: 1 with left child 2 and right child 3; 3 has children 4 and 5

Goal: Convert the tree into a string and then rebuild the same tree from that string

Step 1: Start serialization at root node 1

Serialized string: '1,'

Why: We record the root value first to start the string

Step 2: Serialize left child 2

Serialized string: '1,2,'

Why: We add left child's value to keep tree structure

Step 3: Serialize left child's left and right children which are null

Serialized string: '1,2,null,null,'

Why: We add 'null' to mark no children, so we know where left subtree ends

Step 4: Serialize right child 3

Serialized string: '1,2,null,null,3,'

Why: We add right child's value to continue tree structure

Step 5: Serialize 3's left child 4 and its null children

Serialized string: '1,2,null,null,3,4,null,null,'

Why: We add left subtree of 3 fully to keep structure

Step 6: Serialize 3's right child 5 and its null children

Serialized string: '1,2,null,null,3,4,null,null,5,null,null,'

Why: We add right subtree of 3 fully to complete serialization

Step 7: Start deserialization from string start

Reading '1', create root node 1

Why: We rebuild root first to start tree

Step 8: Deserialize left subtree: read '2', create node 2, then two 'null's for children

Left subtree rebuilt as node 2 with no children

Why: We rebuild left subtree exactly as it was

Step 9: Deserialize right subtree: read '3', create node 3

Right subtree root node 3 created

Why: We rebuild right subtree root

Step 10: Deserialize 3's left child '4' and its null children

Node 4 created as left child of 3 with no children

Why: We rebuild left child of 3

Step 11: Deserialize 3's right child '5' and its null children

Node 5 created as right child of 3 with no children

Why: We rebuild right child of 3

Result:

Tree rebuilt exactly as:
    1
   / \
  2   3
     / \
    4   5

Annotated Code

DSA Python

from typing import Optional

class TreeNode:
    def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                vals.append('null')  # mark null to keep structure
                return
            vals.append(str(node.val))  # record node value
            dfs(node.left)  # serialize left subtree
            dfs(node.right)  # serialize right subtree

        vals = []
        dfs(root)
        return ','.join(vals) + ','  # comma separated string

    def deserialize(self, data: str) -> Optional[TreeNode]:
        def dfs() -> Optional[TreeNode]:
            val = next(vals)
            if val == 'null' or val == '':
                return None  # null means no node here
            node = TreeNode(int(val))  # create node
            node.left = dfs()  # build left subtree
            node.right = dfs()  # build right subtree
            return node

        vals = iter(data.split(','))
        return dfs()

# Driver code to test
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
codec = Codec()
serialized = codec.serialize(root)
print(serialized)
deserialized_root = codec.deserialize(serialized)

# Helper to print tree inorder for verification
def inorder(node):
    if not node:
        return 'null'
    return f'{node.val} -> {inorder(node.left)} -> {inorder(node.right)}'

print(inorder(deserialized_root))

if node is None: vals.append('null') return

mark null to keep tree structure during serialization

vals.append(str(node.val))

record current node's value

dfs(node.left)

serialize left subtree recursively

dfs(node.right)

serialize right subtree recursively

val = next(vals) if val == 'null': return None

read next value; if null, no node here during deserialization

node = TreeNode(int(val))

create node from value

node.left = dfs()

build left subtree recursively

node.right = dfs()

build right subtree recursively

Output

1,2,null,null,3,4,null,null,5,null,null,

1 -> 2 -> null -> null -> 3 -> 4 -> null -> null -> 5 -> null -> null

Complexity Analysis

Time: O(n) because we visit each node once during serialization and once during deserialization

Space: O(n) because the serialized string and recursion stack store all nodes

vs Alternative: Compared to storing only values without nulls, this method keeps structure exactly but uses more space

Edge Cases

Empty tree (root is None)

Serialize returns 'null,' and deserialize returns None

DSA Python

if node is None:
    vals.append('null')
    return

Tree with single node

Serialize records value and two nulls for children; deserialize rebuilds single node

DSA Python

if val == 'null':
    return None

Tree with only left or only right children

Nulls mark missing children so structure is preserved

DSA Python

vals.append('null')

When to Use This Pattern

When you need to save or send a tree and later rebuild it exactly, use serialize/deserialize pattern to convert between tree and string.

Common Mistakes

Mistake: Not recording nulls during serialization, causing loss of tree shape
Fix: Add explicit 'null' markers for missing children to keep structure

Mistake: Splitting serialized string incorrectly or missing trailing comma
Fix: Use consistent delimiter and handle empty strings carefully

Summary

It converts a binary tree into a string and back to the same tree.

Use it when you want to save or transfer a tree structure exactly.

The key is to record null children so the shape is not lost.

Practice

1. What is the main purpose of serialize and deserialize functions in the context of a binary tree?

easy

A. Delete all nodes in a binary tree

B. Sort the nodes of a binary tree

C. Calculate the height of a binary tree

D. Convert a binary tree to a string and back to a tree

Solution

1. Step 1: Understand serialization

   Serialization means converting a data structure like a binary tree into a string format that can be stored or transmitted.

2. Step 2: Understand deserialization

   Deserialization means converting the string back into the original binary tree structure.

3. Final Answer:

   Convert a binary tree to a string and back to a tree -> Option D

4. Quick Check:

   Serialize + Deserialize = Convert tree to string and back [OK]

Hint: Serialization means tree to string, deserialization reverses it [OK]

Common Mistakes:

• Confusing serialization with sorting
• Thinking it deletes nodes
• Mixing serialization with height calculation

2. Which of the following is the correct way to represent a null node during serialization in a binary tree using preorder traversal?

easy

A. Use a special marker like '#' or 'null'

B. Skip the null node completely

C. Use an empty string ''

D. Use the value 0

Solution

1. Step 1: Understand null node representation

   During serialization, null nodes must be marked explicitly to preserve tree structure.

2. Step 2: Choose correct marker

   Common practice is to use a special marker like '#' or 'null' to represent null nodes.

3. Final Answer:

   Use a special marker like '#' or 'null' -> Option A

4. Quick Check:

   Null nodes marked with '#' or 'null' [OK]

Hint: Mark null nodes explicitly with '#' or 'null' [OK]

Common Mistakes:

• Skipping null nodes loses tree shape
• Using empty string confuses parsing
• Using 0 can be mistaken for a valid node

3. Given the following serialized string of a binary tree using preorder with '#' as null marker: 1,2,#,#,3,4,#,#,5,#,#, what is the inorder traversal of the deserialized tree?

medium

A. [2, 4, 1, 3, 5]

B. [1, 2, 3, 4, 5]

C. [2, 1, 4, 3, 5]

D. [1, 3, 2, 4, 5]

Solution

1. Step 1: Reconstruct the tree from serialization

   The string represents preorder: root=1, left=2, left's children null, right=3, left=4, right=5.

2. Step 2: Perform inorder traversal (left, root, right)

   Inorder: left subtree (2), root (1), left subtree of right child (4), root of right child (3), right subtree (5) -> [2, 1, 4, 3, 5]

3. Final Answer:

   [2, 1, 4, 3, 5] -> Option C

4. Quick Check:

   Inorder of deserialized tree = [2, 1, 4, 3, 5] [OK]

Hint: Draw tree from preorder, then do inorder traversal [OK]

Common Mistakes:

• Mixing preorder and inorder orders
• Ignoring null markers during reconstruction
• Swapping left and right children

4. Consider this buggy deserialize function snippet for a binary tree serialized with preorder and '#' as null marker:

def deserialize(data):
    def helper():
        val = next(vals)
        if val == '#':
            return None
        node = TreeNode(int(val))
        node.left = helper()
        node.right = helper()
        return node
    vals = iter(data.split(','))
    return helper()

What is the likely cause of a StopIteration error during deserialization?

medium

A. The helper function does not return the root node

B. The input string is missing some null markers

C. The split method is used incorrectly

D. The TreeNode constructor is called with a string instead of int

Solution

1. Step 1: Understand StopIteration cause

   StopIteration occurs when iterator runs out of elements unexpectedly.

2. Step 2: Check input data correctness

   If null markers '#' are missing, helper calls next(vals) more times than available, causing StopIteration.

3. Final Answer:

   The input string is missing some null markers -> Option B

4. Quick Check:

   Missing '#' causes StopIteration [OK]

Hint: Check if all null nodes are marked to avoid StopIteration [OK]

Common Mistakes:

• Thinking helper must return root explicitly
• Blaming split method for StopIteration
• Confusing int conversion error with StopIteration

5. You want to serialize a binary tree and then deserialize it back. However, the tree can contain negative and zero values. Which serialization approach below correctly handles all integer values including zero and negative numbers without confusion?

hard

A. Serialize using preorder with comma-separated values and 'null' for null nodes

B. Serialize using comma-separated values but skip null nodes

C. Serialize using preorder with space-separated values and '#' for null nodes

D. Serialize using preorder with comma-separated values and '0' for null nodes

Solution

1. Step 1: Identify safe null marker

   Using '0' as null marker is unsafe because zero can be a valid node value.

2. Step 2: Choose clear null marker and separator

   Using 'null' as null marker with comma separator clearly distinguishes null nodes and supports negative and zero values.

3. Final Answer:

   Serialize using preorder with comma-separated values and 'null' for null nodes -> Option A

4. Quick Check:

   'null' marker avoids confusion with zero or negative values [OK]

Hint: Use 'null' marker, not '0', to handle zero and negatives [OK]

Common Mistakes:

• Using '0' as null marker causes confusion
• Skipping null nodes loses tree shape
• Using space separator can cause parsing issues