Serialize and Deserialize Binary Tree in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Serialization Using Preorder Traversal

What is the output of the following serialization code for the given binary tree?

Tree structure:
1
/ \
2 3
/ \
4 5

DSA Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def serialize(root):
    def helper(node):
        if not node:
            return 'N'
        return str(node.val) + ',' + helper(node.left) + ',' + helper(node.right)
    return helper(root)

root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
print(serialize(root))

A "1,2,N,N,3,4,N,N,5,N,N"

B "1,3,2,N,N,4,N,N,5,N,N"

C "1,2,N,N,3,5,N,N,4,N,N"

D "1,3,4,N,N,5,N,N,2,N,N"

💡 Hint

Think about preorder traversal: root, left subtree, then right subtree. Use 'N' for null nodes.

The serialization uses preorder traversal. Starting at root 1, then left child 2 (which has no children), then right child 3 with children 4 and 5. Null children are marked as 'N'.

❓ Predict Output

intermediate

Result of Deserializing a Serialized String

Given the serialized string "1,2,N,N,3,4,N,N,5,N,N", what is the value of the right child of the root after deserialization?

DSA Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

root = deserialize("1,2,N,N,3,4,N,N,5,N,N")
print(root.right.val if root and root.right else None)

A 4

B 2

C 3

D 5

💡 Hint

The root's right child is the node after the left subtree in preorder.

The root is 1. Its left child is 2. After finishing left subtree, next node is 3 which is the right child of root.

🔧 Debug

advanced

Identify the Error in Deserialization Code

What error will the following deserialization code produce when given the input "1,2,N,N,3,4,N,N,5,N,N"?

DSA Python

def deserialize(data):
    nodes = data.split(',')
    def helper():
        val = nodes.pop(0)
        if val == 'N':
            return None
        node = TreeNode(int(val))
        node.left = helper()
        node.right = helper()
        return node
    return helper()

root = deserialize("1,2,N,N,3,4,N,N,5,N,N")

A No error, runs correctly

B TypeError

C IndexError

D ValueError

💡 Hint

Check how the list is consumed during recursion.

Using pop(0) removes the first element each time, so the list shrinks correctly and recursion works without error.

❓ Predict Output

advanced

Output of Serialization Using Level Order Traversal

What is the output of the following serialization code using level order traversal (BFS) for the given binary tree?

Tree structure:
1
/ \
2 3
/ \
4 5

DSA Python

from collections import deque

def serialize(root):
    if not root:
        return ''
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node:
            result.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append('N')
    return ','.join(result)

root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
print(serialize(root))

A "1,3,2,4,5,N,N,N,N,N,N"

B "1,2,3,N,N,4,5,N,N,N,N"

C "1,2,3,4,5,N,N,N,N,N,N"

D "1,2,3,N,N,N,N,4,5"

💡 Hint

Level order visits nodes level by level, left to right. Use 'N' for missing children.

The queue processes nodes in order: 1, then 2 and 3, then their children. Null children are marked as 'N'.

🧠 Conceptual

expert

Why Use Null Markers in Tree Serialization?

Why is it necessary to include null markers (like 'N') when serializing a binary tree using preorder traversal?

A To sort the nodes during deserialization

B To reduce the size of the serialized string by skipping null nodes

C To mark nodes that have only one child

D To indicate the end of a branch so the tree structure can be uniquely reconstructed

💡 Hint

Think about how the deserialization knows where left subtree ends and right subtree begins.

Null markers show where branches end, allowing the deserialization to rebuild the exact tree shape.

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