Serialize and Deserialize a Binary Tree

Question

Design an algorithm to serialize a binary tree to a string and deserialize it back. Tests tree traversal and string parsing skills, a recurring Google question.

Codemia · Accepted Answer

The problem at hand requires serializing a binary tree into a string format and then deserializing it back to reconstruct the original tree. The key pattern that applies here is the use of depth-first traversal (DFS) to both serialize and deserialize the tree. This is because we can leverage the recursive nature of trees to easily traverse each node and its children, storing the values in a specific format during serialization (e.g., pre-order) and reconstructing them during deserialization. This ensures that we capture the structure of the tree accurately.

1. **Serialization**: We will use a pre-order traversal (node -> left -> right) to serialize the tree. During traversal, we will append the value of each node to a list, using a placeholder (e.g., 'null') for null nodes to maintain tree structure.
   - Example: For a tree like this:
     
         1
        / \
       2   3
      / 
     4   
   The serialized output will be: '1,2,4,null,null,null,3,null,null'

2. **Deserialization**: We will split the serialized string by commas to create a list of values. We will then recursively build the tree using these values, ensuring to handle 'null' placeholders appropriately to reconstruct the tree structure.
   - Example: The string '1,2,4,null,null,null,3,null,null' will be converted back to the original tree by recursively creating nodes based on the order of values in the list.

Here is the Python solution for the serialization and deserialization of a binary tree:

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

class Codec:
    def serialize(self, root):
        values = []
        def dfs(node):
            if node:
                values.append(str(node.val))
                dfs(node.left)
                dfs(node.right)
            else:
                values.append('null')
        dfs(root)
        return ','.join(values)

def deserialize(self, data):
        values = data.split(',')
        def build_tree():
            val = next(values)
            if val == 'null':
                return None
            node = TreeNode(int(val))
            node.left = build_tree()
            node.right = build_tree()
            return node
        return build_tree()
```
This code defines a `TreeNode` class for the nodes and a `Codec` class with methods to serialize and deserialize the binary tree.

The time complexity for both serialization and deserialization is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during serialization and reconstruction during deserialization. The space complexity is also O(n) due to the storage of node values in a list during serialization and the recursion stack during deserialization, which can go as deep as the height of the tree (which in the worst case is n for a skewed tree).

1. **Empty Tree**: If the input tree is empty, the serialization should return 'null', and deserialization from 'null' should return None.
   - Input: `None` -> Output: 'null'
   - Input: 'null' -> Output: `None`

2. **Single Node Tree**: A tree with only one node should serialize to '1,null,null' and deserialize back to a single node.
   - Input: `TreeNode(1)` -> Output: '1,null,null'
   - Input: '1,null,null' -> Output: `TreeNode(1)`

Serialize and Deserialize a Binary Tree

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string