Framework Thinking - Neetcode 150 - Serialize and Deserialize Binary Tree

Here is solutions for Serialize and Deserialize Binary Tree.

1. Understand the problem

You are given a binary tree. You must:

Serialize it: convert the tree into a string.
Deserialize it: convert that string back into the same original tree structure.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

Can node values be negative or large?

Yes — assume any 32-bit integer.

Can the tree be empty?

Yes — root = None must be handled.

Is the tree guaranteed to be a BST?

No — it’s a general binary tree.

Do we control the output format of serialization?

Yes — we can design any format.

Do duplicate values appear?

Yes — so structure matters, not just values.

3. Explore examples.

Example 1:

Serialization:

"1,2,#,#,3,4,#,#,5,#,#"

Example 2:

Serialization:

"1,#,#"

Example 3:

None

Serialization:

"#"

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 — Preorder DFS with Null Markers (Most Common) - Time O(N), Space O(N)

Key Idea
- Use preorder traversal (Node → Left → Right):
- When you see a real node → write its value.
- When you see None → write a special marker like “#”.
Time: O(N).
Space: O(N).

4.2. Solution 2 - Level Order (BFS) Serialization - Time O(N), Space: O(N)

1,2,3,#,#,4,5

Time: O(N).
Space: O(N).

4.3. Solution 3 - Optimize for BST - Time O(N), Space O(N) but do not need to store NULL

A Binary Search Tree has the strict rule:

left subtree < root < right subtree

So in a BST:
- Preorder traversal = root is always the first value
- All following values smaller than root must belong to the left subtree
- All larger values must belong to the right subtree
- Do not need to store NULL but you can reorder it by value.
Time: O(N).
Space O(N).

5. Implement solutions.

5.1. DFS - Time O(N), Space O(H)

Idea: It is completed binary tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Codec:

    # Encodes a tree to a single string.
    def serialize(self, root: Optional[TreeNode]) -> str:
        res = []

        def dfs(node):
            if not node:
                res.append("#")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(res)

    # Decodes your encoded data to tree.
    def deserialize(self, data: str) -> Optional[TreeNode]:
        vals = data.split(",")
        self.i = 0

        def dfs():
            if vals[self.i] == "#":
                self.i += 1
                return None
            node = TreeNode(int(vals[self.i]))
            self.i += 1
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

Time: O(N).
Space O(H).

5.2. BFS - Time O(N), Space O(N)

Idea: It is completed binary tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Codec:

    # Encodes a tree to a single string.
    def serialize(self, root: Optional[TreeNode]) -> str:
        if not root:
            return "N"
        res = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if not node:
                res.append("N")
            else:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        return ",".join(res)

    # Decodes your encoded data to tree.
    def deserialize(self, data: str) -> Optional[TreeNode]:
        vals = data.split(",")
        if vals[0] == "#":
            return None
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        index = 1
        while queue:
            node = queue.popleft()
            if vals[index] != "#":
                node.left = TreeNode(int(vals[index]))
                queue.append(node.left)
            index += 1
            if vals[index] != "#":
                node.right = TreeNode(int(vals[index]))
                queue.append(node.right)
            index += 1
        return root

Time: O(N).
Space O(N).

6. Dry run testcases.

Step	Node	Action	Output List
1	1	add value	`["1"]`
2	2	add value	`["1","2"]`
3	None	add `#`	`["1","2","#"]`
4	None	add `#`	`["1","2","#","#"]`
5	3	add value	`["1","2","#","#","3"]`
6	4	add value	`["1","2","#","#","3","4"]`
7	None	add `#`	`["1","2","#","#","3","4","#"]`
8	None	add `#`	`["1","2","#","#","3","4","#","#"]`
9	5	add value	`["1","2","#","#","3","4","#","#","5"]`
10	None	add `#`	`["1","2","#","#","3","4","#","#","5","#"]`
11	None	add `#`	`["1","2","#","#","3","4","#","#","5","#","#"]`

December 4, 2025