🎄297. Serialize and Deserialize Binary Tree
Hard | Grind 75 | January 13th Friday, 2023
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.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Constraints:
The number of nodes in the tree is in the range
[0, 10^4].-1000 <= Node.val <= 1000
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]SOLUTION
Serialize: To begin, we will initialize a variable called "serialized" to store the serialized string representation of the Tree. We will utilize a Breadth-First Search (BFS) method to traverse the tree level by level. As we iterate through each node, we will append its value with a trailing comma to the "serialized" variable. If the node is empty, we will instead append the letter "N" with a trailing comma to indicate a null value in the tree.
Deserialize: We have serialized the value of each node with a trailing comma, thus allowing us to split the string based on commas to create a list that contains the values of the nodes in the tree. The first element of this list is the root of the tree, and the next two elements at indices 1 and 2 are its left and right children, respectively. Additionally, the elements at indices 3 and 4 are the left and right children of the root's left child, and so on. To construct the tree, we will process one node at a time from our queue and use an index to iterate over the list to obtain the current node's children. We will take the two elements, create nodes if not None, and then add them to our queue. This process will continue until the queue is empty or we have iterated over all the elements in the list.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
serialized = ""
if root:
queue = deque()
queue.append(root)
while queue:
curr = queue.popleft()
# if the node is not None
if curr:
serialized += f"{str(curr.val)},"
queue.append(curr.left)
queue.append(curr.right)
# need to serialized even if None. only it wont be added to queue
else:
serialized += "N,"
return serialized
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if data:
# split the string to list
data = data.split(",")
# last element is empty due to data format
data.pop()
root = TreeNode(int(data[0]))
queue = deque()
queue.append(root)
# iterator for the data list.
index = 1
while queue and index < len(data):
#process two continuous elements at a time
curr = queue.popleft()
# the first element if not N will be the left child
if data[index] != "N":
left_child = TreeNode(int(data[index]))
curr.left = left_child
queue.append(left_child)
index += 1
# the second element if not N will be the right child
if index < len(data) and data[index] != "N":
right_child = TreeNode(int(data[index]))
curr.right = right_child
queue.append(right_child)
index += 1
return root
return
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))TIME AND SPACE COMPLEXITY
TIME: O(n) where n is the number of nodes. In serialization, we iterate over every node once. Similarly, in deserialization, we iterate over the length of the data which is the number of nodes once.
SPACE: O(n) where n is the number of nodes. In serialization, we use a queue that will at most have n elements. In deserialization, we use another queue that will again at most hold n elements.
* Written with help from ChatGPT *
Last updated