Serialize and Deserialize Binary Tree

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.

For example, you may serialize the following tree 1 / 2 3 / 4 5 as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ 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.

In this approach a BFS traversal is used, with some modifications to catch the leaf elements (None)

# 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
        """
        if root is None:
            return ""
        serial_list = []
        self.serializeHelper(root, serial_list)
        return ' '.join(serial_list) # join with a space as the delimiter

    def serializeHelper(self, root, serial_list):
        from collections import deque

        q = deque()
        q.append(root)
        while q:
            item = q.popleft()
            if item == "N":
                serial_list.append(item)
                continue

            serial_list.append(str(item.val))

            if item.left:
                q.append(item.left)
            else:
                q.append("N")

            if item.right:
                q.append(item.right)
            else:
                q.append("N")

        #print 'serial_list: ', serial_list


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

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

        data = data.split() # split the data string with space as the delimiter

        from collections import deque
        q = deque()

        n = TreeNode(int(data[0])) #root
        q.append(n)

        for i in xrange(len(data)):
            item = q.popleft()
            #///////////////////////////////////////////////////
            # since the serialization is level ordered, the children
            # will occur at the 2*i+1 and 2*i+2 location in the array
            #///////////////////////////////////////////////////
            j_idx = 2*i + 1
            k_idx = 2*i + 2

            if data[j_idx] != "N":
                #print 'j_idx: ', j_idx, 'data[j_idx]: ', data[j_idx]
                item.left = TreeNode(int(data[j_idx]))
                q.append(item.left)
            else:
                item.left = None

            #////////////////////////////////////////////////// 
            #terminating condition
            #//////////////////////////////////////////////////
            if j_idx >= len(data) - 2:
                break

            if data[k_idx] != "N":
                item.right = TreeNode(int(data[k_idx]))
                q.append(item.right)
            else:
                item.right = None

        return n        



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

Another awesome solution using pre-order traversal: Ref:

class Codec:

    def serialize(self, root):
        def doit(node):
            if node:
                vals.append(str(node.val))
                doit(node.left)
                doit(node.right)
            else:
                vals.append('#')
        vals = []
        doit(root)
        return ' '.join(vals)

    def deserialize(self, data):
        def doit():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = doit()
            node.right = doit()
            return node
        vals = iter(data.split())
        return doit()