DSA With AI
Week 4 ยท Trees

Serialize and Deserialize Binary Tree

Encode a binary tree into a string and decode it back into the same structure. The runner asks you to round-trip a nested tree and return the rebuilt tree.

Hard Trees Week 4 Practice runner

Frame the problem

  • Tree shape must be preserved, not just values.
  • Empty children need explicit representation.
  • The serializer and deserializer formats only need to agree with each other.
1. Reveal example inputs and outputs

Example 1

Input:

serialize_and_deserialize([
  1,
  [
    2,
    null,
    null
  ],
  [
    3,
    [
      4,
      null,
      null
    ],
    [
      5,
      null,
      null
    ]
  ]
])

Output:

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

Example 2

Input:

serialize_and_deserialize(null)

Output:

null
2. Brute force first

What information is lost if you serialize only the non-null values in preorder?

3. Reveal the insight ladder
  1. Preorder records root before its children.
  2. A null marker records where an empty child appears.
  3. During deserialization, read tokens in the same preorder order.
  4. Each non-null token recursively consumes exactly its left and right subtree tokens.
4. Dry run before code
  1. Tree [1, 2, 3] with missing children.
  2. Preorder with null markers starts 1, 2, #, #, 3, #, #.
  3. The decoder reads 1, then fully rebuilds left child 2, then right child 3.
  4. Null markers stop child recursion at the correct places.
5. Reveal final Python solution 
def serialize_and_deserialize(root):
    values = []

    def serialize(node):
        if node is None:
            values.append("#")
            return
        value, left, right = node
        values.append(str(value))
        serialize(left)
        serialize(right)

    def deserialize():
        token = next(tokens)
        if token == "#":
            return None
        return [int(token), deserialize(), deserialize()]

    serialize(root)
    tokens = iter(values)
    return deserialize()

Complexity: Time O(n), space O(n) for the serialized tokens and recursion stack.

Interview narration

  • I will choose preorder because it gives the root before both subtrees.
  • Null markers are the key to preserving shape.
  • The decoder mirrors the encoder, so each token is consumed exactly once.

Common traps

  • Omitting null markers and making different shapes collide.
  • Using a delimiter that cannot handle arbitrary string values without escaping in non-integer variants.
  • Using pop(0) on a Python list repeatedly instead of an iterator or deque.

Follow-up drills

1. Could level-order serialization work?

Yes. Use a queue and include null markers for missing children. It may include trailing nulls that you can trim if your decoder handles that convention.

2. How would this change for arbitrary string values?

Use length-prefix encoding or JSON tokens so delimiters inside values cannot corrupt parsing.

3. Why is the format not required to match LeetCode's display format?

The problem only requires deserialize(serialize(root)) to rebuild the original tree. Any unambiguous internal format is acceptable.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.