Serialize and Deserialize Binary Tree (LC297)

06 May 2019

Problem description

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:

You may serialize the following tree:

1    / \   2   3
 / \
4   5

as “[1,2,3,null,null,4,5]” Clarification: The above 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.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution

I’ve used Level Order Traversal to serialize and deserialize the binary tree

Below is my python implementation

# 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
        """
        ans = []
        current = root
        queue = collections.deque()
        queue.append(root)
        if root == None:
            return ""
        while queue:
            node = queue.popleft()
            if node:
                ans.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                ans.append('null')
        return ','.join(ans)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == "":
            return None
        ans = data.split(',')
        queue = collections.deque()
        i = 0
        root = TreeNode(int(ans[0]))
        queue.append(root)
        while queue:
            node = queue.popleft()
            if node:
                i += 1
                if ans[i] == 'null':
                    queue.append(None)
                else:
                    left = TreeNode(int(ans[i]))
                    node.left = left
                    queue.append(left)
                i += 1
                if ans[i] == 'null':
                    queue.append(None)
                else:
                    right = TreeNode(int(ans[i]))
                    node.right = right
                    queue.append(right)
            else:
                pass
        return root
                
        
        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))