Serialize and Deserialize Binary Tree

The problem description can be found in LeetCode.

Approach

We can use DFS to serialize all the nodes and deserialize them back to get the original tree.

For the following tree:

We would need to generate a string like:

[1, 2, 4, 5, 3, 6, 7]

As you can see, we will prioritize the nodes on the left sub-tree and then proceed with the ones onthe right.

Solution

from typing import List, Optional, Tuple


class Codec:
    NULL_NODE = "null"
    NODE_SEP = ","

    def serialize(self, root: Optional[TreeNode]) -> str:
        def dfs(node: Optional[TreeNode], nodes) -> None:
            if not node:
                nodes.append(Codec.NULL_NODE)
            else:
                nodes.append(str(node.val))
                dfs(node.left, nodes)
                dfs(node.right, nodes)

        nodes: List[str] = []
        dfs(root, nodes)

        return Codec.NODE_SEP.join(nodes)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        def dfs(i: int) -> Tuple[int, Optional[TreeNode]]:
            if nodes[i] == Codec.NULL_NODE:
                i += 1
                return i, None

            node = TreeNode(nodes[i])
            i += 1

            i, left_node = dfs(i)
            i, right_node = dfs(i)

            node.left = left_node
            node.right = right_node

            return i, node

        i = 0
        nodes = data.split(Codec.NODE_SEP)
        _, root = dfs(i)

        return root

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the number of nodes in the tree.