Skip to content

Save and Restore the Tree

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 2 (Click for link to problem statements)

Save and Restore the Tree

A binary tree must be written to a string so it can be sent over the network and rebuilt exactly. Implement both directions: serialize turns a tree into a string, and deserialize rebuilds the identical tree from that string.

You may design the string format however you like, as long as a round trip reproduces the original tree.

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

class Codec:
    def serialize(self, root):
        pass

    def deserialize(self, data):
        pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Binary Trees, Depth-First Search (DFS), Preorder Traversal, String Encoding

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: Do we have to produce one specific string format?
    • A: No. Any format is acceptable as long as deserialize(serialize(root)) reconstructs a tree identical to the original, node for node.
  • Q: What must the string capture so the tree can be rebuilt exactly?
    • A: Both the node values and the tree's shape. A plain list of values is not enough — we must also record where the missing (None) children are so the structure is unambiguous.
  • Q: Can the tree be empty, and can values be negative or multi-digit?
    • A: Yes to both. serialize(None) should produce a string that deserialize turns back into None, and the format needs a delimiter so values like -10 or 700 are not confused with single digits.
HAPPY CASE
Input:
      1
     / \
    2   3
       / \
      4   5
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
data = codec.serialize(root)
rebuilt = codec.deserialize(data)
Output: codec.serialize(rebuilt) == data evaluates to True
Explanation: Serializing the tree, deserializing the string, and serializing again produces the exact same string, so the round trip reproduced the original tree.

EDGE CASE
Input: root = None (an empty tree)
Output: deserialize(serialize(None)) returns None
Explanation: The codec must handle a tree with no nodes at all.

Input: root = TreeNode(1, None, TreeNode(2, None, TreeNode(3))) (a right-skewed tree)
Output: The rebuilt tree is identical — every left child is None and the values 1, 2, 3 chain down the right side.
Explanation: Skewed trees expose formats that fail to record missing children; without None markers, this tree is indistinguishable from other shapes with the same values.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Binary Tree Serialization Problems, we can consider the following approaches:

  • Preorder DFS with None markers: Walk the tree root-left-right, writing each value and writing a sentinel (like "N") for every missing child. Preorder is ideal because the first token is always the subtree's root, which makes rebuilding a natural recursion.
  • BFS (level-order) with None markers: Encode the tree level by level using a queue; also valid, but requires more bookkeeping when rebuilding.
  • Recursion / Divide and Conquer: Both serialize and deserialize decompose into "handle the root, then recurse on the left subtree, then the right subtree."

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Serialize with a preorder DFS, emitting each node's value and the sentinel "N" for every None child, joined by commas. Because every missing child is recorded, the string encodes the tree's exact shape. To deserialize, split the string into tokens and consume them left to right with the same preorder recursion: read a token, and if it is "N" return None; otherwise create a node and recursively build its left then right subtree. The token order guarantees each recursive call consumes exactly the tokens for its own subtree.

serialize(root):
1) Create an empty list of tokens.
2) DFS from the root in preorder:
   a) If the node is None, append "N" and return.
   b) Append the node's value as a string.
   c) Recurse on the left child, then the right child.
3) Join the tokens with commas and return the string.

deserialize(data):
1) Split the string on commas and create an iterator over the tokens.
2) Define a recursive build function:
   a) Take the next token.
   b) If it is "N", return None.
   c) Otherwise create a TreeNode from the token's integer value.
   d) Recursively build the node's left subtree, then its right subtree.
   e) Return the node.
3) Return the result of the first build call.

⚠️ Common Mistakes

  • Serializing only the values without None markers — different tree shapes then produce the same string and cannot be told apart.
  • Forgetting a delimiter between values, so 1,2 and 12 become ambiguous, or negative signs break single-character parsing.
  • Building the left and right subtrees in a different order in deserialize than they were written in serialize.
  • Re-scanning the token list with an index reset in each recursive call instead of consuming tokens once, in order.
  • Not handling the empty tree, causing deserialize to crash on the string "N".

4: I-mplement

Implement the code to solve the algorithm.

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

class Codec:
    def serialize(self, root):
        # Preorder DFS; record None children as "N" so the shape is unambiguous
        parts = []
        def dfs(node):
            if node is None:
                parts.append("N")
                return
            parts.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ",".join(parts)

    def deserialize(self, data):
        # Consume tokens in the same preorder they were written
        tokens = iter(data.split(","))
        def build():
            token = next(tokens)
            if token == "N":
                return None
            node = TreeNode(int(token))
            node.left = build()
            node.right = build()
            return node
        return build()

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))

    • serialize visits the nodes in preorder: 1, 2, (N, N), 3, 4, (N, N), 5, (N, N).
    • data becomes "1,2,N,N,3,4,N,N,5,N,N".
    • deserialize reads 1 (root), then 2 (left child), then N,N (2 is a leaf), then 3 (right child), then 4 with N,N, then 5 with N,N — rebuilding the exact original shape.
    • codec.serialize(rebuilt) == data → Output: True, matching the expected example output.

  • Input: root = None

    • serialize returns "N", and deserialize("N") reads the single token and returns None. The round trip holds for the empty tree.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of nodes in the tree and H is its height.

  • Time Complexity: O(N) for both serialize and deserialize — each node (and each None child slot, of which there are N + 1) is visited exactly once.
  • Space Complexity: O(N) for the token list and output string, plus O(H) for the recursion stack, which degrades to O(N) for a skewed tree.

Clone this wiki locally