Serialize and Deserialize Binary Tree

Serializing and deserializing a binary tree is an interesting problem that involves converting a tree into a string (or some other data structure) and then reconstructing the tree from that string.

Serialization:

For serialization, we can perform a level-order traversal of the tree and append the value of each node to a string. If a node is None, we can append a special character (e.g., "null") to the string.

Here’s the code to serialize a binary tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def serialize(self, root):
    if not root:
        return ""

    queue = [root]
    result = []

    while queue:
        node = queue.pop(0)
        if node:
            result.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append("null")

    return ",".join(result)

Deserialization:

For deserialization, we’ll split the string by commas and then use a queue to reconstruct the tree level by level.

Here’s the code to deserialize a string back to a binary tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def deserialize(self, data):
    if not data:
        return None

    nodes = data.split(",")
    root = TreeNode(int(nodes[0]))
    queue = [root]
    i = 1

    while queue and i < len(nodes):
        node = queue.pop(0)
        if nodes[i] != "null":
            left = TreeNode(int(nodes[i]))
            node.left = left
            queue.append(left)
        i += 1
        if nodes[i] != "null":
            right = TreeNode(int(nodes[i]))
            node.right = right
            queue.append(right)
        i += 1

    return root

Explanation:

Serialization involves traversing the tree level by level and converting it into a string. We use “null” to represent missing nodes.
Deserialization involves reading the string and reconstructing the tree level by level.

Key Takeaways:

The time complexity for both serialization and deserialization is (O(n)), where (n) is the number of nodes in the tree.
The space complexity is also (O(n)) due to the storage of the result string and the use of a queue.
This approach ensures that the original tree structure is perfectly preserved and can be reconstructed from the serialized string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ""

        queue = [root]
        result = []

        while queue:
            node = queue.pop(0)
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")

        return ",".join(result)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None

        nodes = data.split(",")
        root = TreeNode(int(nodes[0]))
        queue = [root]
        i = 1

        while queue and i < len(nodes):
            node = queue.pop(0)
            if nodes[i] != "null":
                left = TreeNode(int(nodes[i]))
                node.left = left
                queue.append(left)
            i += 1
            if nodes[i] != "null":
                right = TreeNode(int(nodes[i]))
                node.right = right
                queue.append(right)
            i += 1

        return root

Traverse the tree, save the values in a data structure
Read the values from the datastructure and construct the string

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val)
#         @val = val
#         @left, @right = nil, nil
#     end
# end

def serialize_wrapper(node, output)
  if node.nil?
      output << 'null,'
      return 
  end
  
  output << "#{node.val},"
  serialize_wrapper(node.left, output)
  serialize_wrapper(node.right, output)
end

# @param {TreeNode} root
# @return {string}
def serialize(root)
  output = ''
  serialize_wrapper(root, output)  
  output
end

def deserialize_wrapper(array)
  first = array.shift
  if (first == 'null')
      return 
  end
  
  node = TreeNode.new(first.to_i) 
    
  node.left = deserialize_wrapper(array)
  node.right = deserialize_wrapper(array)
  
  return node
end

# Decodes your encoded data to tree.
# @param {string} data
# @return {TreeNode}
def deserialize(data)
    array = data.split(',')
    
    deserialize_wrapper(array)
end

Identifying Problem Isomorphism

“Serialize and Deserialize Binary Tree” can be mapped to “Encode and Decode TinyURL”.

In “Serialize and Deserialize Binary Tree”, we have to take a binary tree, converting it into a string representation (serialize), and then reconstructing the original binary tree from that string representation (deserialize). This requires understanding binary trees and how to traverse them in order to construct the serialized form.

“Encode and Decode TinyURL” is about creating a shortened string representation of a longer URL (encode) and then reconstructing the original URL from the shortened representation (decode). It involves mapping long URLs to their shorter counterparts and maintaining this map for encoding and decoding purposes.

The reason for this mapping is that both problems deal with the concept of transforming a data structure or piece of information into a more compact form and the ability to reverse this process. “Serialize and Deserialize Binary Tree” is more complex as it requires an understanding of tree traversal techniques, whereas “Encode and Decode TinyURL” is simpler and primarily involves string manipulations and utilizing a hash map.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Codec:
    def serialize(self, root):
        flat_bt = []
        queue = collections.deque([root])
        while queue:
            node = queue.pop()
            if node:
                flat_bt.append(str(node.val))
                queue.appendleft(node.left)
                queue.appendleft(node.right)
            else:

                flat_bt.append('')
        return ','.join(flat_bt)

    def deserialize(self, data):
        if not data:
            return
        flat_bt = data.split(',')
        ans = TreeNode(flat_bt[0])
        queue = collections.deque([ans])
        i = 1

        while queue:
            node = queue.pop()
            if i < len(flat_bt) and flat_bt[i]:
                node.left = TreeNode(int(flat_bt[i]))
                queue.appendleft(node.left)
            i += 1
            if i < len(flat_bt) and flat_bt[i]:
                node.right = TreeNode(int(flat_bt[i]))
                queue.appendleft(node.right)
            i += 1
        return ans

Language Agnostic Coding Drills

Drill 1: Understanding Binary Trees: The first step is understanding what a binary tree is. You can start by building a binary tree data structure, adding nodes to it, and printing the values of these nodes.
Drill 2: Breadth-First Search (BFS) Traversal: The next step involves mastering the BFS traversal algorithm, which visits all the nodes of a tree (or graph) level by level. This is the key to both the serialization and deserialization processes in the solution.
Drill 3: Serialization: Learn how to transform a data structure or object state into a format that can be stored. In this case, the binary tree is being converted into a string.
Drill 4: Deserialization: Practice reversing the process of serialization. This means taking the serialized string and reconstructing the original binary tree from it.
Drill 5: Queues and Deques: Understand how to use a queue or a deque (double-ended queue) in your language of choice. You’ll use a queue (or deque) to hold nodes at each level during your BFS traversal. For serialization, you start with the root node in the queue. For deserialization, you start with the root node of the new tree you’re building.
Drill 6: Handling None or Null values: In this problem, ’null’ or ‘None’ values are used to indicate that a node doesn’t have a left or right child. It’s important to handle these cases correctly when you’re serializing and deserializing.
Drill 7: String Manipulation: Get comfortable with the string manipulation functions in your language of choice. In this problem, you’re converting between comma-separated strings and lists of node values.

Problem-solving Approach:

Understand how a binary tree is structured and how the BFS traversal algorithm works.
For serialization, start the BFS traversal with the root node. Visit each node in the tree, adding the value of each node to your output string. If a node doesn’t have a left or right child, add a placeholder to your string.
For deserialization, start with the root node and do a BFS traversal again. This time, instead of visiting the nodes of an existing tree, you’re building up a new tree one node at a time.
Keep track of which node values you’ve used and which ones you still need to add to the tree.
When you’re done, you should have a new tree that has the same structure as the original tree.

Targeted Drills in Python

Drill 1: Understanding Binary Trees

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# create root node
root = TreeNode(1) 
# add left child to root node
root.left = TreeNode(2) 
# add right child to root node
root.right = TreeNode(3)

In this drill, you’re simply creating a binary tree with a root node and two child nodes.

Drill 2: Breadth-First Search (BFS) Traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from collections import deque

def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft() # dequeuing happens from the left
        print(node.val, end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
bfs(root)

In this drill, you’re implementing a BFS traversal algorithm to visit and print all nodes in the tree.

Drill 3: Serialization

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def serialize(root):
    queue = deque([root])
    result = []
    while queue:
        node = queue.popleft()
        if node:
            result.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append('#')
    return ','.join(result)

print(serialize(root))

In this drill, you’re converting a binary tree into a string.

Drill 4: Deserialization

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def deserialize(data):
    if data[0] == '#':
        return None
    nodes = data.split(',')
    root = TreeNode(int(nodes[0]))
    queue = deque([root])
    index = 1
    while queue:
        node = queue.popleft()
        if nodes[index] != '#':
            node.left = TreeNode(int(nodes[index]))
            queue.append(node.left)
        index += 1

        if nodes[index] != '#':
            node.right = TreeNode(int(nodes[index]))
            queue.append(node.right)
        index += 1
    return root

In this drill, you’re converting a serialized string back into a binary tree.

Drill 5: Queues and Deques

1
2
3
4
5
queue = deque(['a', 'b', 'c'])
queue.append('d') # ['a', 'b', 'c', 'd']
queue.appendleft('z') # ['z', 'a', 'b', 'c', 'd']
queue.pop() # 'd', queue = ['z', 'a', 'b', 'c']
queue.popleft() # 'z', queue = ['a', 'b', 'c']

In this drill, you’re practicing the usage of deque for queue operations.

Drill 6: Handling None or Null values

1
2
3
4
5
6
# assuming 'serialize' function from Drill 3
serialized_data = serialize(root)
if serialized_data is None:
    print('Nothing to deserialize')
else:
    root = deserialize(serialized_data)

In this drill, you’re checking for None or null values before deserialization.

Drill 7: String Manipulation

1
2
3
data = '1,2,3'
list_data = data.split(',') # ['1', '2', '3']
string_data = ','.join(list_data) # '1,2,3'

In this drill, you’re practicing basic string manipulations like splitting a string into a list and joining a list into a string.