Practice: Serialize and Deserialize Binary Tree

Problem: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Recognition reminder: this is a design problem, not a single function. You build a class with two methods that are inverses of each other: serialize flattens a tree into a string, deserialize rebuilds the identical tree from that string. The whole difficulty is the tree’s shape: a flattening that records only the present values cannot tell a left-only child from a right-only one, so you must record where the missing children are with an explicit null marker.

Before you start (the five-beat rhythm)

  1. Your Pattern Card for this week is already written.
  2. Name the pattern aloud and write your approach as a plain-English comment before any code.
  3. Struggle floor: 25 minutes unaided. No hints, no AI, no Discuss tab.
  4. If stuck past the floor, ask the tutor for a hint. Six rungs, one per ask.
  5. Debrief in your commit message before moving to the next problem.

Your target

Fill these in yourself before you look at anyone else’s solution:

Target time complexity (serialize):    ____
Target time complexity (deserialize):  ____
Target space complexity:               ____

Each method visits every node a constant number of times, so think about what that forces for time. The string you produce, and the structure you read it back through, are both proportional to the number of nodes; name what dominates the space.

The interface you implement

Write a class Codec in a file named solution.py in this folder (your own work repo, not the course repo). It supports:

Codec()                       # initialize (no state needed)
serialize(root) -> str        # turn a tree (root TreeNode or None) into a string
deserialize(data: str) -> root  # rebuild the tree from that string, return its root

The only contract that matters is the round-trip: deserialize(serialize(root)) must reproduce a tree identical to root, in both values and shape. The format of the string is entirely your choice (a pre-order walk with a marker for each None is a common one, but any reversible scheme is fine). Because the format is yours, the test does not check the exact string; it checks that the round-trip rebuilds the same tree.

Decide your null marker and your separator deliberately. You need to be able to split the string back into tokens unambiguously, and you need a token that means “no node here” so the shape survives. Pick a traversal for serialize and use the matching reconstruction for deserialize (if you write the nodes in pre-order, rebuild them in pre-order); the two methods are a matched pair, and a mismatch is the classic bug.

Where your code goes

Write your Codec class in solution.py in your own work repo (see getting-started.md), not in the course repo. Define your own TreeNode class (the same three-attribute shape the test uses) so your methods can build and read nodes. This folder ships only the problem spec and a provided-example test (tests/test_provided.py). Because this is a design problem and serialization formats vary, the test does not assert any exact string: it builds a tree, runs it through deserialize(serialize(tree)), and asserts the rebuilt tree equals the original by a structural level-order comparison (values and shape, including where the nulls are). Run it locally before you submit to LeetCode’s judge. The judge is the oracle; the tutor will not confirm your answer by reading it.

Debrief (paste into your commit message) 

1. What pattern did this turn out to be?
2. What was the trigger phrase or input shape that should have made me reach for it?
3. What was the time and space complexity, and what would dominate at scale?
4. What edge case would have broken my first attempt?
5. What would I do differently in three days when I see this cold?