DSA sheet · Trees · Serialize & construction pattern

Serialize & Deserialize Binary Tree

This is the last problem of the serialize/construction pattern. We write two functions that work as a pair. Serialize turns a tree into a string. Deserialize takes that same string and rebuilds the exact same tree. The teacher doesn't hand over the final format. She tries a simple string first, shows why it breaks, fixes it, shows the next problem, and fixes that too. By the end we see why every comma and every null marker is needed. The final solution is a preorder traversal on both sides.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the format from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Serialize (tree → string) with preorder
• Part B · Deserialize (string → tree) with preorder
• Part C · Revision page

Part 0 · Before starting

What does "serialize" mean?

A tree lives in memory as nodes joined by pointers. You can't directly save pointers to a file or send them over a network. Serializing means writing the tree down as plain text (a string). Deserializing means reading that text back and rebuilding the nodes and pointers. The only rule: deserialize(serialize(tree)) must give back the same tree, with the same values and the same shape.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

The three traversals (prerequisite)

• Preorder: root, left, right.
• Inorder: left, root, right.
• Postorder: left, right, root.

The teacher says this video assumes you already know these three traversals well. If not, learn them first.

Part A · Serialize (tree → string) with preorder

LeetCode 297

1The question in simple words

• serialize(root): return a string that stores the whole tree.
• deserialize(data): given that string, rebuild the tree and return its root.
• You choose the string format. It only has to round-trip correctly.

Our example tree for the whole page:

      1
     / \
    2   3
       / \
      4   5

2What the constraints tell us

• Nodes: 0 to 10⁴ → the tree can be empty. Then there's nothing to store, and deserializing must give back None.
• n up to 10⁴ means n² = 10⁸, which is right at the TLE line and too slow. So we aim for a linear O(n) solution.
• Values: −1000 to 1000. They fit easily in an int, and we never add or multiply them. But note: values can be negative and have several digits, so in the string a value is more than one character. Remember this in step 4.

3Intuition: write the tree in an order you can replay

We already know three ways to list every node: pre, in and post order. The teacher picks preorder. Its big advantage: the root always comes first. When we read the string back, the first value we meet is the root, then its whole left subtree, then its whole right subtree. That is exactly the order in which we can build nodes: make the root, then build its left, then build its right.

4Building the format from examples (three attempts)

Attempt 1: just write the values → broken

Preorder of the tree: 1, 2, 3, 4, 5. Written together: "12345".

Reading it back, we can't tell where one number ends. Was it 1, 2, 3, 4, 5? Or 12, 3, 45? Or 123, 4, 5? With multi-digit and negative values allowed, this is hopeless.

Attempt 2: values with commas → still broken

Now we know the values, but not the shape. Rebuild with preorder: 1 is the root. The next value, 2, must be its left child (preorder goes left after root). Then 3 is… 2's left child? Or 1's right child? The string doesn't say. Nothing tells us that 2 has no children. If we keep assuming "left", we build this wrong tree:

      1
     / \
    2   3
       / \
      4   5

          1
         /
        2
       /
      3
     /
    4
   /
  5

The missing piece is: where are the empty spots? Leaves, and nodes with only one child, have empty (None) children, and we never wrote them down.

Attempt 3: values + commas + # for None → works

Do preorder again, and write # every time we step into an empty child:

• 1 → write 1. Go left.
• 2 → write 2. 2's left is empty → #. 2's right is empty → #.
• Back to 1, go right: 3 → write 3. Go left.
• 4 → write 4, then #, # (leaf).
• 5 → write 5, then #, # (leaf).

Now every node is followed by exactly the information about its two children, so the shape is fixed. In short: commas tell us what the values are, and # tells us where the tree is empty.

5Approach steps (serialize)

1. If the node is None → return "#".
2. Otherwise return: the node's value, a comma, the serialized left subtree, a comma, the serialized right subtree.

6Code (Python)

class Codec:
    def serialize(self, root):
        if root is None:
            return "#"
        # root , left , right  (preorder)
        return str(root.val) + "," + self.serialize(root.left) + "," + self.serialize(root.right)

7Code line by line

In the video she says "inorder" for a moment while writing this. It's a slip: root, left, right is preorder.

8Dry run

s(x) = serialize(x). Each call waits for its left and right calls to finish, then joins the pieces.

1. s(2) → "2," + s(None) + "," + s(None) = "2,#,#".
2. s(4) → "4,#,#" and s(5) → "5,#,#" (both leaves).
3. s(3) → "3," + "4,#,#" + "," + "5,#,#" = "3,4,#,#,5,#,#".
4. s(1) → "1," + "2,#,#" + "," + "3,4,#,#,5,#,#" = "1,2,#,#,3,4,#,#,5,#,#" ✓

9Complexity & remember

• Time O(n): each node (and each None spot) is visited once.
• Space O(n): the output string has n values plus n + 1 markers. The recursion stack is O(height).

Part B · Deserialize (string → tree) with preorder

1The question

Input: a string made by our serialize, e.g. "1,2,#,#,3,4,#,#,5,#,#". Output: the root of the rebuilt tree.

2What the constraints tell us

• The string "#" means an empty tree → return None. Our code handles this without a special check (the very first token is #).
• Tokens can be "-12" or "1000", so we must split on commas, not read one character at a time.

3Intuition: replay the preorder with one moving pointer

Split the string on commas into a list of tokens. Keep one index i that moves forward through the list, and is shared by all the recursive calls. Each call takes the next token:

• If it's # → this spot is empty, return None.
• Otherwise → make a node with that value, then build its left subtree from the next tokens, then its right subtree.

Because serialize wrote root, left, right, reading back in the same order puts every token in the right place.

4Building the logic from the example

• Token 0 = 1 → the root. Next comes 1's left.
• Token 1 = 2 → 1.left = 2. Next comes 2's left.
• Token 2 = # → 2.left = None. Next is 2's right.
• Token 3 = # → 2.right = None. 2 is finished, go back to 1 and do 1's right.
• Token 4 = 3 → 1.right = 3. Token 5 = 4 → 3.left = 4. Tokens 6, 7 = #, # → 4 is a leaf.
• Token 8 = 5 → 3.right = 5. Tokens 9, 10 = #, # → 5 is a leaf.
• The index has passed the end. Return the root, 1.

5Approach steps (deserialize)

1. arr = data.split(","), i = 0.
2. build(): read arr[i], then i += 1.
3. If the token is "#" → return None.
4. Otherwise make TreeNode(int(token)), set left = build(), then right = build().
5. Return the node. deserialize returns build() of the first token.

6Code (Python)

class Codec:
    def serialize(self, root):
        if root is None:
            return "#"
        return str(root.val) + "," + self.serialize(root.left) + "," + self.serialize(root.right)

    def deserialize(self, data):
        self.arr = data.split(",")      # "1,2,#" -> ["1", "2", "#"]
        self.i = 0                      # shared index into arr
        return self.build()

    def build(self):
        val = self.arr[self.i]          # take the next token
        self.i += 1                     # ...and move past it
        if val == "#":
            return None
        root = TreeNode(int(val))       # "-7" -> -7
        root.left = self.build()        # next tokens describe the left subtree
        root.right = self.build()       # then the right subtree
        return root

7Code line by line

8Dry run with the index

1. b() reads 1 (i → 1) → make node 1, build its left.
2. b() reads 2 (i → 2) → make node 2, build its left.
3. b() reads # (i → 3) → None. 2.left = None. Build 2's right.
4. b() reads # (i → 4) → None. 2.right = None. Node 2 returns → 1.left = 2.
5. Build 1's right: b() reads 3 (i → 5) → node 3, build its left.
6. b() reads 4 (i → 6) → node 4. Its left reads # (i → 7), its right reads # (i → 8). 4 returns → 3.left = 4.
7. 3's right: b() reads 5 (i → 9) → node 5. Its children read # (i → 10) and # (i → 11). 5 returns → 3.right = 5.
8. 3 returns → 1.right = 3. 1 returns. The tree is rebuilt ✓, and i = 11, so exactly all tokens were used.

9Complexity & remember

• Time O(n): we read each token once and create each node once.
• Space: the recursion stack holds one call per level → O(height). But the token list from split holds about 2n + 1 strings → O(n). So overall it's O(n).

Part C · Revision page

class Codec:
    def serialize(self, root):
        out = []
        def pre(node):
            if node is None:
                out.append("#")
                return
            out.append(str(node.val))
            pre(node.left)
            pre(node.right)
        pre(root)
        return ",".join(out)

    def deserialize(self, data):
        tokens = iter(data.split(","))      # next(tokens) plays the role of arr[i++]
        def build():
            val = next(tokens)
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        return build()

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

c = Codec()
s = c.serialize(root)
print(s)                                   # 1,2,#,#,3,4,#,#,5,#,#
print(c.serialize(c.deserialize(s)) == s)  # True
print(c.deserialize(c.serialize(None)))    # None

Based on this video: Serialize and Deserialize Binary Tree