My Vault

tree-serialize

2 min read

Tree Serialization

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

BFS

Serialize level by level. Mark the children of leaves as null.

def serialize(root):
    if not root:
        return ""
    output = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node:
            output.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        else:
            output.append('n')
    return ','.join(output)
 
def deserialize(data):
    if not data:
        return None
 
    nodes = data.split(',')
    root = TreeNode(int(nodes[0]))
    queue = deque([root])
    index = 1
 
    while queue and index < len(nodes):
        node = queue.popleft()
 
        if nodes[index] != 'n':
            node.left = TreeNode(int(nodes[index]))
            queue.append(node.left)
        index += 1
 
        if index < len(nodes) and nodes[index] != 'n':
            node.right = TreeNode(int(nodes[index]))
            queue.append(node.right)
        index += 1
 
    return root

A simpler deserialize version. Intuition: use queue to remember the parents to attach the new nodes to.

def deserialize(self, data):
    if not data:
        return None
    
    nodes = data.split(',')
    root = TreeNode(int(nodes.pop(0)))
    queue = [root]
    
    while nodes:
        parent = queue.pop(0)
        
        left_val = nodes.pop(0) if nodes else 'n'
        if left_val != 'n':
            parent.left = TreeNode(int(left_val))
            queue.append(parent.left)
        
        if nodes:
            right_val = nodes.pop(0)
            if right_val != 'n':
                parent.right = TreeNode(int(right_val))
                queue.append(parent.right)
    
    return root

DFS

Can be preorder, inorder, or postorder. More natural compared to BFS when deserialize.

def serialize(root):
    def rserialize(root, string):
        if root is None:
            string += 'None,'
        else:
            string += str(root.val) + ','
            string = rserialize(root.left, string)
            string = rserialize(root.right, string)
        return string
    
    return rserialize(root, '')
def deserialize(data):
    def rdeserialize(l):
        if l[0] == 'None':
            l.pop(0)
            return None
            
        root = TreeNode(l.pop(0))
        root.left = rdeserialize(l)
        root.right = rdeserialize(l)
        return root
 
    data_list = data.split(',')
    root = rdeserialize(data_list)
    return root

Graph View