Skip to main content
SeniorPath
Browse content
Menu / Close menu

March 24

Serialize and Deserialize Binary Tree

How to turn a tree into a string and back while preserving the null markers that define its shape.

Trees Advanced 30 min TypeScript

#interviews#trees#dfs#design

Implement serialization and deserialization for a binary tree.

In the original problem, this usually appears as a Codec class with:

  • serialize(root): string
  • deserialize(data): TreeNode | null

In the SeniorPath playground, use:

  • runCodec(root)

And return an object with:

  • serialized: the serialized string
  • deserialized: the reconstructed tree

To keep output deterministic, use:

  • preorder
  • # for null
  • , as the separator

Example:

Input:  root = [1,2,3,null,null,4,5]
Output: serialized = "1,2,#,#,3,4,#,#,5,#,#"

Deserialization must rebuild the same original structure.

What to notice before coding

  • Storing only the values is not enough. The `null` markers carry structural information.
  • Serialization and deserialization must agree on the same protocol.
  • Preorder works well because you write and read the tree in the same recursive flow.

Common mistakes

  • omitting `null` markers and losing structural information
  • deserializing tokens without a shared position

Step 1 - Understand what must survive

A common first thought is:

  • "I will save the tree values"

That is not enough.

Two different trees can share the same values in similar orders.

What must survive is:

  • the values
  • the structure

Step 2 - Write a simple protocol

A good protocol here is:

  • preorder
  • a normal value for a real node
  • # for null

Example:

  • node 1
  • then left
  • then right

That gives you a sequence that already carries the tree shape.

Step 3 - Start with the most direct version

The most direct way to deserialize is:

  • split the string into tokens
  • use shift() to consume the next item
  • rebuild recursively

It works.

But in JavaScript, shift() on an array costs O(n), because it moves everything else.

Step 4 - Replace shift() with a cursor

The protocol does not need to change.

Only the reading strategy changes:

  • instead of removing the first token every time
  • keep an index called position
  • read tokens[position] and advance

Same idea. No hidden array cost.

The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.

Starter code

export function runCodec(root) {
  // root is an object like { val: number, left: ..., right: ... } or null
  // return { serialized: string, deserialized: tree }
  return { serialized: "", deserialized: null }
}
solution.ts
Stuck? Hints available.

Haven't solved it yet?

Viewing the solution now may reduce learning. It's worth trying a bit more.

Open the reference solution

Without JavaScript, the reference solution is shown inline instead of in a dialog.

Solution

Final complexity

Time: O(n)

Space: O(n)

Solution 1 - Preorder plus shift() on the way back

Good baseline because it makes the protocol very visible.

function serialize(root) {
  if (root === null) {
    return "#"
  }

  return `${root.val},${serialize(root.left)},${serialize(root.right)}`
}

function deserialize(data) {
  const tokens = data.split(",")

  function build() {
    const token = tokens.shift()

    if (token === "#" || token === undefined) {
      return null
    }

    return {
      val: Number(token),
      left: build(),
      right: build(),
    }
  }

  return build()
}

export function runCodec(root) {
  const serialized = serialize(root)

  return {
    serialized,
    deserialized: deserialize(serialized),
  }
}

It works.

But shift() makes deserialization more expensive than it looks.

Solution 2 - Preorder plus cursor with DFS in O(n)

Now the protocol stays the same, but the read is truly linear.

function serialize(root) {
  if (root === null) {
    return "#"
  }

  return `${root.val},${serialize(root.left)},${serialize(root.right)}`
}

function deserialize(data) {
  const tokens = data.split(",")
  let position = 0

  function build() {
    const token = tokens[position]
    position += 1

    if (token === "#") {
      return null
    }

    return {
      val: Number(token),
      left: build(),
      right: build(),
    }
  }

  return build()
}

export function runCodec(root) {
  const serialized = serialize(root)

  return {
    serialized,
    deserialized: deserialize(serialized),
  }
}

The strong insight here is that serialization and deserialization are two halves of the same contract.

What to say in the interview

A strong short explanation would be:

I use preorder with a null marker because that preserves both values and structure. On the way back, I read the tokens in the same recursive order. The stronger version avoids shift() and uses a shared cursor so the whole parse stays O(n).

That shows that you:

  • thought in terms of protocol, not only traversal
  • protected the tree structure
  • noticed a hidden implementation cost

When this pattern shows up again

This pattern comes back when you need to:

  • turn structure into a transportable representation
  • rebuild state from a protocol
  • decide which structural information must be explicit
  • use DFS as both the writing and the reading order

The point is not memorizing Codec.

The point is learning that good serialization starts with the right contract.
Next challenge Find Median from Data Stream Previous challenge Spiral Matrix

Related challenges

Invert Binary Tree

Binary Tree Level Order Traversal

Maximum Depth of Binary Tree

Related articles

Thinking Before You Code in Interviews

How to Explain Your Solution Without Getting Lost

Recognizing Problem Patterns