HardBlind75TreeBFSDesign

Serialize and Deserialize Binary Tree

Design an algorithm to serialize and deserialize a binary tree to a string and back.

Examples

Input
serialize(root) where root = [1,2,3,null,null,4,5]
Output
'1,2,null,null,3,4,null,null,5,null,null'

Serialize the tree to a string using preorder traversal.

Input
deserialize('1,2,null,null,3,4,null,null,5,null,null')
Output
[1,2,3,null,null,4,5]

Deserialize the string back to the tree.

Constraints

  • •The number of nodes in the tree is in the range [0, 10^4]
  • •-1000 <= Node.val <= 1000

Approaches

Use BFS to serialize, including null markers.

CodeT: O(n) | S: O(n)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import deque

class Codec:
    def serialize(self, root):
        if not root:
            return 'null'
        result = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append('null')
        return ','.join(result)
    def deserialize(self, data):
        if data == 'null':
            return None
        vals = data.split(',')
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            if vals[i] != 'null':
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if vals[i] != 'null':
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1
        return root

Use preorder traversal for serialization.

CodeT: O(n) | S: O(n)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root):
        if not root:
            return 'null'
        return str(root.val) + ',' + self.serialize(root.left) + ',' + self.serialize(root.right)
    def deserialize(self, data):
        def dfs():
            val = next(vals)
            if val == 'null':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        vals = iter(data.split(','))
        return dfs()

Same DFS approach with cleaner implementation.

Diagram

Tree: 1->2,3->null,null and 4->null,null 5->null,null Serialize: '1,2,null,null,3,4,null,null,5,null,null' Deserialize: rebuilds same tree structure
CodeT: O(n) | S: O(n)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root):
        if not root:
            return 'null'
        return f'{root.val},{self.serialize(root.left)},{self.serialize(root.right)}'
    def deserialize(self, data):
        def helper(it):
            val = next(it)
            if val == 'null':
                return None
            node = TreeNode(int(val))
            node.left = helper(it)
            node.right = helper(it)
            return node
        return helper(iter(data.split(',')))

Complexity Comparison

BFS - Level Order with Nulls
T: O(n)S: O(n)

Use BFS to serialize, including null markers.

DFS - Preorder
T: O(n)S: O(n)

Use preorder traversal for serialization.

Optimized DFS
T: O(n)S: O(n)

Same DFS approach with cleaner implementation.

Common Mistakes

Not handling null nodes in the serialization

Using a delimiter that could appear in node values

Not preserving the tree structure during deserialization

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems