Watch 10 video solutions for Serialize and Deserialize Binary Tree, a hard level problem involving String, Tree, Depth-First Search. This walkthrough by NeetCode has 161,913 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = [] Output: []
Constraints:
[0, 104].-1000 <= Node.val <= 1000Problem Overview: Design two functions: one converts a binary tree into a string (serialize), and the other reconstructs the same tree from that string (deserialize). The structure of the tree must remain identical after reconstruction, including null children.
Approach 1: Depth‑First Search Serialization (Preorder) (Time: O(n), Space: O(n))
This approach performs a preorder traversal: visit the current node, then the left subtree, then the right subtree. During serialization, append node values to a string and insert a special marker such as # for null children. The key insight is that preorder traversal combined with explicit null markers uniquely represents the tree structure. During deserialization, read tokens sequentially and rebuild the tree recursively: create a node for a value and recursively construct its left and right children. Every node and null placeholder is processed exactly once, giving O(n) time and O(n) space for recursion and storage. This method is common when working with Depth-First Search on a Binary Tree.
Approach 2: Breadth‑First Search Serialization (Level Order) (Time: O(n), Space: O(n))
This approach uses level-order traversal with a queue. During serialization, push the root into a queue and process nodes level by level. Append each node's value to the output string, and insert a placeholder such as # when a child is missing. For deserialization, read the values sequentially and reconstruct the tree by attaching left and right children while dequeuing parent nodes. The queue ensures nodes are connected in the same order they appeared in the level traversal. This method mirrors how many tree problems are solved using Breadth-First Search, and it often feels more intuitive because it directly follows the tree’s level structure.
Both strategies rely on encoding null nodes explicitly. Without null markers, different trees could produce identical serialized sequences, making reconstruction impossible.
Recommended for interviews: The preorder DFS approach is the most common expectation. It demonstrates clear understanding of tree traversal, recursion, and structural encoding. The BFS approach also runs in O(n) time and is equally valid, but interviewers usually prefer the recursive preorder method because the serialization and deserialization logic aligns naturally with tree structure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Preorder Serialization | O(n) | O(n) | Preferred interview solution; simple recursive reconstruction of tree structure |
| BFS Level Order Serialization | O(n) | O(n) | Useful when thinking in level traversal or implementing iterative queue-based logic |