How do you approach Serialize and Deserialize Binary Tree?

Use preorder traversal for serialization.

What is the time complexity of Serialize and Deserialize Binary Tree?

Time complexity: O(n). Space complexity: O(n).

What are common mistakes on Serialize and Deserialize Binary Tree?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Serialize and Deserialize Binary Tree

HardData Structures

Description

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. **Note:** For this problem, implement serialize() to convert a tree array to a string, and deserialize() to convert it back.

Example 1

Input: root = [1,2,3,null,null,4,5]

Output: [1,2,3,null,null,4,5]

Explanation: Serialize the tree and deserialize it back to the same structure.

Example 2

Input: root = []

Output: []

Constraints

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

Serialize and Deserialize Binary Tree: approach, complexity and pitfalls

A hard trees problem, graded against 5 test cases (2 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Use preorder traversal for serialization.
Use a delimiter to separate values and a marker for null nodes.
For deserialization, recursively rebuild the tree in the same order.

The optimal approach

Show the approach: Preorder Traversal

Serialize using preorder traversal with a special marker for null nodes. Deserialize by processing the string in the same preorder fashion.

Time: O(n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.