Serialise And Deserialise Binary Tree

Question

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example 1:

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

Solution

This question is different than Construct Binary Tree from Preorder and Inorder Traversal because it allows you to put in the null node as you go. Therefore we know exactly which node is the children of which node.

So in theory, you should be able to do a preorder to serialise and create the binary tree in the same time. For example.

[!important]
The reason why we choose preorder instead of other is because when re-creating the tree, preorder gives us access to the root first to put in the left and right child

This tree here if we do preorder traversal should be read as following:

1, 2, null, 3, null, null, 4, 5, null, 6, 7, null, null

And when we read this list back, we can just build using preorder as well, it should work, for example

1, 2, null, 3, null, null, 4, 5, null, 6, 7, null, null
^

                   1

1, 2, null, 3, null, null, 4, 5, null, 6, 7, null, null
   ^

                   1
            2

1, 2, null, 3, null, null, 4, 5, null, 6, 7, null, null
        ^

                   1
            2
       null

1, 2, null, 3, null, null, 4, 5, null, 6, 7, null, null
            ^

                   1
            2
       null    3

1, 2, null, 3, null, null, 4, 5, null, 6, 7, null, null
                ^

                   1
            2
       null    3
              /
            null


1, 2, null, 3, null, null, 4, 5, null, 6, 7, null, null
                      ^

                   1
            2
       null    3
              /  \
            null  null

And so on

Implementation

from collection import deque
from typing import *

class App:
    def serialize(self, root) -> List[int]:
        self.encodedString = []
        self._serialize(root)
        return ",".join(self.encodedString)

    def _serialize(self, root):
        if not root: 
            self.encodedString.append("None")
            return

        self.encodedString.append(str(root.val))
        self._serialize(root.left)
        self._serialize(root.right)

    def deserialize(self, data: List[int]) -> 'TreeNode':
        return self._deserialize(deque(data.split(",")))
    
    def _deserialize(self, data: Deque[int]) -> 'TreeNode':
        if not data: return None
        
        currValue = data.popleft()

        if currValue == "None": 
            return None
        
        node = TreeNode(currValue)
        node.left = self._deserialize(data)
        node.right = self._deserialize(data)

        return node

Time complexity: $O(n)$ — Since we have to go through n node of the tree for both deserialise and serialise

Space complexity: $O(n)$ — Since we have to store the encoded string in and recursion heap