Skip to main content

297. Serialize and Deserialize Binary Tree

hard

Encode a binary tree to a string and decode it back. The shape MUST roundtrip, including null structure. Pre-order with explicit null markers is the cleanest fit; the tokenizer trick on deserialize keeps the code tight.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

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

Example 2

Input
root = []
Output
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Plain pre-order (root, left, right) alone is ambiguous — many trees produce the same sequence. You need a sentinel for null children.

Hint 2

Serialize: pre-order DFS, append node.val (or 'N' for null) plus a delimiter. Deserialize: consume tokens left-to-right, recursing on left then right.

Hint 3

Using a queue or iterator for the token stream makes deserialize a clean two-line recursion.

Solution approach

Reveal approach

Pre-order with null markers. Serialize(node): if null, append 'N,' and return. Otherwise append node.val + ',' then recurse into left then right. Top-level call returns the joined string. Deserialize(data): split data on ',' to get a token array (or use a generator/iterator/queue for cleanest code). Helper build(): take the next token. If it's 'N', return null. Otherwise create a node with that value, set node.left = build(), node.right = build(), return node. Top-level returns build() consumed against the token stream. Because every node — including null children — emits exactly one token, the recursion knows precisely how to split tokens between left and right subtrees. O(n) time and O(n) space for both directions.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • tree-dfs
  • tree-bfs
  • design
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • LinkedIn
  • Uber

More Trees practice problems

See all Trees problems →