Serialize and Deserialize Binary Tree

Table of Contents +

Imagine you want to send a tree to a friend over the internet. You cannot send a drawing. You can only send text. So you must turn the tree into a string. Your friend must turn that string back into the exact same tree. That round trip is this question. The catch is making sure the string holds enough information to rebuild the shape perfectly.

🎯 The Problem

You need two functions. Serialize means turn a tree into a string. Deserialize means turn that string back into the same tree.

The rules:

  • Serialize turns a tree into a string.
  • Deserialize turns that string back into the same tree.
  • The rebuilt tree must match the original exactly: same values, same shape, same left and right sides.
  • The hard part is the shape. Values alone lose the structure.
  • So the string must record the empty spots too, or you cannot rebuild the shape.

Let us use a small tree. The root is 1. Its left child is 2. Its right child is 3. The 3 has children 4 and 5.

Input (the tree):
        1
       / \
      2   3
         / \
        4   5


Serialized string: "1,2,#,#,3,4,#,#,5,#,#"


Deserialized: the exact same tree is rebuilt.

The # symbol marks an empty spot, which is a missing child. The commas just separate the items. Reading the string left to right gives the tree in preorder, which is root first, then left, then right.

Here is the tree we are encoding.

1

2

3

4

5

🐢 Approach 1: Store Values Only (Brute Force)

Store just the values in one order, like an inorder list.

The idea:

  • Write down every node value in a single fixed order.
  • No markers, no shape info.

Why it is weak:

  • Values alone do not point to one single shape.
  • Many different trees produce the same value list.
  • So you cannot rebuild the original for sure.

Here is the rejected values-only sketch:

serialize_values_only_wrong.py
def serialize_values_only(root):
    values = []
    def dfs(node):
        if node:
            values.append(str(node.val))
            dfs(node.left); dfs(node.right)
    dfs(root)
    return ",".join(values)

🧩 Approach 2: Store Two Traversals (Better)

The idea in one line: store preorder and inorder together, then rebuild the shape from both.

The idea:

  • Two traversals pin down the structure for many trees.
  • Preorder gives the roots. Inorder splits left from right.

How it works:

  • Save both lists.
  • Use them together to reconstruct each subtree.

Why it is fragile:

  • It breaks when values repeat, because you cannot tell which copy is which.
  • It costs more space and needs more careful code.
  • We want one method that always works.

Here is the preorder/inorder code:

serialize_two_traversals.py
def serialize(root):
    preorder, inorder = [], []
    def pre(node):
        if node: preorder.append(node.val); pre(node.left); pre(node.right)
    def ino(node):
        if node: ino(node.left); inorder.append(node.val); ino(node.right)
    pre(root); ino(root)
    return str((preorder, inorder))

⚡ Approach 3: Preorder With Null Markers (Best)

The idea in one line: walk in preorder and write a marker for every empty spot, so the string describes every position.

The idea:

  • Preorder means root first, then left side, then right side.
  • For each real node, write its value.
  • For each missing child, write a marker like #.
  • Join everything with commas.

How it works:

  • The string now describes every position, full or empty.
  • To rebuild, read items in the same order with a moving pointer.
  • A value makes a node. A # returns an empty spot and ends that branch.
  • Rebuild the left child, then the right child, from the same stream.

Why it is best:

  • The markers tell the rebuilder exactly where each branch ends.
  • The preorder order lines up perfectly, so the pointer never gets confused.
  • It always works, even when values repeat.

Here is the rebuild flow, showing how each item from the string becomes a node or an empty spot.

yes

no

read next item

is it a hash mark?

return empty spot

make node with that value

rebuild left child from stream

rebuild right child from stream

Steps to Solve

  1. To serialize, walk the tree in preorder.
  2. Write each node’s value. For a missing child, write the marker #.
  3. Join all the pieces with commas into one string.
  4. To deserialize, split the string back into a list of items.
  5. Keep a pointer at the front of that list.
  6. Take the next item. If it is #, return an empty spot.
  7. Otherwise make a node with that value.
  8. Rebuild its left child, then its right child, from the same list. Return the node.

This Python version builds a list of items during preorder, joins them into a string, then reads them back with a moving iterator.

serialize_tree.py
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None




def serialize(root):
    parts = []


    def walk(node):
        if not node:                 # missing child
            parts.append("#")
            return
        parts.append(str(node.val))  # value
        walk(node.left)              # left side
        walk(node.right)             # right side


    walk(root)
    return ",".join(parts)           # join with commas




def deserialize(data):
    items = iter(data.split(","))    # stream of items


    def build():
        tok = next(items)            # take next item
        if tok == "#":               # empty spot
            return None
        node = Node(int(tok))
        node.left = build()          # rebuild left
        node.right = build()         # rebuild right
        return node


    return build()




root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(5)


text = serialize(root)
print(text)


rebuilt = deserialize(text)
print("root=" + str(rebuilt.val)
      + " left=" + str(rebuilt.left.val)
      + " right=" + str(rebuilt.right.val))

The output of the above code will be:

1,2,#,#,3,4,#,#,5,#,#
root=1 left=2 right=3

Let us walk through the Python version line by line, since the round trip is the whole point.

In serialize, the line parts = [] collects the pieces of the string. We add to this list as we walk.

The inner walk function does the preorder walk. The line if not node: parts.append("#") writes the marker for a missing child. This is the key step. Without it, the empty spots would vanish and the shape would be lost. The line parts.append(str(node.val)) writes a real value. Then walk(node.left) and walk(node.right) write the left side and the right side, in that order.

The line return ",".join(parts) glues every piece with commas. So we get 1,2,#,#,3,4,#,#,5,#,#.

In deserialize, the line items = iter(data.split(",")) turns the string back into a stream of items. An iterator hands out one item at a time when we call next.

Inside build, the line tok = next(items) takes the next item from the stream. The line if tok == "#": return None handles an empty spot. When we see the marker, we return nothing, which ends that branch.

If the item is a value, the line node = Node(int(tok)) makes the node. Then node.left = build() rebuilds the left child from the same stream. After the left side is fully done, node.right = build() rebuilds the right child. The preorder order in the string lines up exactly with this left-then-right rebuild. So the pointer always reads the right item at the right time.

⏱️ Time and Space Complexity

Both functions touch each node once, plus the empty markers, which there are a fixed number of per node. So serialize and deserialize each run in O(n) time. The space is O(n) too, for the string and the recursion stack. The slow guess methods either fail on repeated values or cost more, so the preorder-with-markers method is the clean win.

Approach Time Complexity Space Complexity
Store values only (cannot rebuild) O(n) O(n)
Two traversals (breaks on repeats) O(n) O(n)
Preorder with null markers O(n) O(n)

Tip

The one rule that makes this work: write a marker for every missing child. People forget the empty spots and then the tree shape cannot be rebuilt. The markers are not optional.

🧩 Key Takeaways

  • ✅ Serialize means tree to string. Deserialize means string back to the same tree.
  • ✅ Walk in preorder, which is root first, then left, then right.
  • ✅ Write a marker like # for every missing child, so the shape is never lost.
  • ✅ To rebuild, read items in order with a moving pointer and recurse left then right.
  • ✅ Both directions run in O(n) time and O(n) space.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why must the serialized string include markers for missing children?

    Why: Without markers for empty spots, you lose the structure and cannot tell where each branch ends, so the original tree cannot be rebuilt.

  2. 2

    In what order does the preorder serialization write the nodes?

    Why: Preorder writes the root first, then the entire left side, then the entire right side.

  3. 3

    When deserializing, what does reading a '#' marker mean?

    Why: A '#' marks a missing child, so the rebuilder returns nothing for that position and that branch ends.

  4. 4

    What is the time complexity of serialize and deserialize here?

    Why: Each function processes every node and its markers exactly once, so both run in O(n) time.

Score: 0 / 4

🚀 What’s Next?

Previous Binary Tree Maximum Path Sum Next Binary Tree Vertical Order Traversal