Serialize and Deserialize Binary Tree
Statement
Serialize a given binary tree, and deserialize it back to a binary tree. The original and deserialized binary tree should be identical.
Constraints
- 0 ≤ number of nodes ≤ 500
- -1000 ≤
node.value≤ 1000
Solution
"""
production algorithm
"""
from data_structures.binary_tree.binary_tree import BinaryTreeNode
class Solution:
def serialize(self, root):
"""
time complexity O(n)
space complexity O(n)
"""
stream = list()
self.serialize_helper(root, stream)
return stream
def serialize_helper(self, root, stream):
"""
time complexity O(n)
space complexity O(n)
"""
if not root:
stream.append(None)
return
stream.append(root.data)
self.serialize_helper(root.left, stream)
self.serialize_helper(root.right, stream)
def deserialize(self, stream):
"""
time complexity O(n)
space complexity O(n)
"""
stream = stream[::-1]
return self.deserialize_helper(stream)
def deserialize_helper(self, stream):
"""
time complexity O(n)
space complexity O(n)
"""
data = stream.pop()
if data is None:
return None
root = BinaryTreeNode(data)
root.left = self.deserialize_helper(stream)
root.right = self.deserialize_helper(stream)
return root"""
unit tests
"""
from unittest import TestCase
from algorithms.dfs.serialize_and_deserialize_binary_tree.solution import Solution
class SolutionTestCase(TestCase):
def test_deserialize_and_serialize(self):
# Given
stream = [1, 2, 4, 8, None, 5, 9, None, 3, 6, 10, None, 7,
11, None, None, None, None, None, None, None, None, None]
solution = Solution()
# When
actual = solution.serialize(solution.deserialize(stream))
# Then
expected = stream
self.assertEqual(actual, expected)Strategy
Depth First Search.
Explanation
Start with serialize. Given a root node, a stream represented as a list is initialized, and then the tree is recursed in preorder traversal. First the data of some root node is appended to the stream, and then the left and right subtrees are recursed in that order. If some root node is null, then append null to the stream. The result is the serialization of the binary tree.
Now, about deserialize. Given a stream, first reverse the stream. The stream is reversed so that elements of the stream can be popped from the stream in constant time. The binary tree is deserialized starting from the root node. If some element popped from the stream is null, then return null as the value of that node. The result is deserialization of the stream of the binary tree.
Time Complexity
In both serialize and deserialize, a length proportional to the number of nodes of the binary tree is iterated. Therefore, the time complexity of the algorithm is O(n).
Space Complexity
In both serialize and deserialize, recursion is used. At most, the depth of recursion is proportional to the number of nodes, in the case of a degenerate tree. Therefore, the auxiliary space complexity of the algorithm is O(n).
