Skip to content

Volume ITechnology

4.14.15 — Serialize and Deserialize Binary Tree ​

LeetCode 297 · Hard · ★ Blind 75

The problem ​

Write a tree to a string, and rebuild the identical tree from that string. The format is yours to choose.

     1
   /   \
  2     3        →  some string  →  the same tree back
       / \
      4   5
      4   5

To put this in plain English: you need to convert a 3D tree structure into a flat 1D string, and then write a function that can read that 1D string and perfectly reconstruct the 3D tree.

Constraints to Keep in Mind: ​

  • 0 <= Number of nodes in the tree <= 10^4
  • -1000 <= Node.val <= 1000
  • The tree can be empty, unbalanced, or huge.

The Naive Approach ​

From a previous problem (Construct Binary Tree from Preorder and Inorder), we know that we can uniquely identify a tree if we have BOTH its preorder and inorder traversals.

  • How it works: To serialize, you could run a preorder traversal and an inorder traversal, joining them both into a string like "pre:1,2,3|in:2,1,3". To deserialize, you'd parse out the two arrays and run the O(n) build function.
  • Why we can do better: While this works, it requires doing two full traversals, storing twice as much data in the string, and running a somewhat complex reconstruction algorithm. We can serialize a tree using only ONE traversal if we simply record the empty spaces (null pointers).

4.14.13 needed two traversals to rebuild a tree, because one alone is ambiguous:

  1        1
 /          \
2            2

Both give pre-order [1, 2].

But the ambiguity only exists because you cannot tell a missing left child from a missing right child. Write the missing children down and it disappears.

  1  →  1, 2, #, #, #        (1, then left=2 with two nulls, then right=null)
 /
2

  1  →  1, #, 2, #, #        (1, then left=null, then right=2)
   \
    2

One traversal is now enough. That is the whole idea, and it is the same insight as 4.4.6 Encode and Decode Strings: make the encoding self-describing and the decoder never has to guess.

Why pre-order ​

Pre-order writes the root first. So the decoder reads a value, creates that node, and then recursively builds its left subtree and its right subtree — consuming the string in exactly the order it was written. The reader needs no lookahead and no index arithmetic.

In-order would not work at all, because the decoder would not know which value is the root of the piece it is reading.

The solution ​

python
class Codec:
    def serialize(self, root) -> str:
        parts = []  # (1)

        def walk(node):  # (2)
            if not node:  # (3)
                parts.append('#')
                return
            parts.append(str(node.val))  # (4)
            walk(node.left)  # (5)
            walk(node.right)

        walk(root)
        return ','.join(parts)  # (6)

    def deserialize(self, data: str):
        values = iter(data.split(','))  # (7)

        def build():  # (8)
            token = next(values)  # (9)
            if token == '#':  # (10)
                return None
            node = TreeNode(int(token))  # (11)
            node.left = build()          # (12) order matters: left, then right
            node.right = build()
            return node  # (13)

        return build()
ts
function serialize(root: TreeNode | null): string {
  const parts: string[] = [];  // (1)
  (function walk(node: TreeNode | null) {  // (2)
    if (!node) { parts.push('#'); return; }  // (3)
    parts.push(String(node.val));  // (4)
    walk(node.left);  // (5)
    walk(node.right);
  })(root);
  return parts.join(',');  // (6)
}

function deserialize(data: string): TreeNode | null {
  const values = data.split(',');  // (7)
  let i = 0;
  function build(): TreeNode | null {  // (8)
    const token = values[i++];  // (9)
    if (token === '#') return null;  // (10)
    const node = new TreeNode(Number(token));  // (11)
    node.left = build();  // (12)
    node.right = build();
    return node;  // (13)
  }
  return build();
}

Line by line ​

Turning the tree into a string.

(1) A list of pieces. We collect the pieces in a list and join them once at the end. Adding to a Python string over and over copies the whole string each time, which adds up to O(n^2) work. Joining a list once is O(n).

(2) A walk in pre-order: visit the node first, then its left subtree, then its right subtree.

(3) A missing child is written as #. This marker is what makes the string describe exactly one tree. Without it, different shapes could produce the same string, as 4.14.5 showed.

(4) Write this node's value.

(5) Then the whole left subtree, then the whole right subtree.

(6) Join the pieces with commas.

Turning the string back into a tree.

(7) Split the string back into pieces, and wrap the list in an iterator. An iterator hands out the pieces one at a time, in order, each time you call next on it. Every recursive call shares this one iterator, so each piece is used exactly once. TypeScript uses a shared position counter, i, for the same job.

(8) The builder. Each call reads exactly the pieces that describe one subtree, and returns that subtree.

(9) Take the next piece.

(10) A # means "no node here".

(11) Otherwise, make a node with this value. The text "12" becomes the number 12.

(12) Build its left subtree, then its right subtree, in the same order they were written. Because each call uses up exactly the pieces of its own subtree, when the left call returns, the iterator is sitting at the first piece of the right subtree.

(13) Return the finished subtree to its parent.

Every node writes exactly three things: its value, its left subtree, its right subtree. A null writes one thing. That regularity is what makes the decoder a mirror image of the encoder.

The iterator (or the index) must be shared across all recursive calls, because each call consumes tokens that the next one must not re-read. Python's iter gives this naturally; TypeScript uses a closure variable.

The comma matters. Joining with nothing would make 1 and 2 indistinguishable from 12. The same delimiter reasoning as 4.4.6 — except here the values are numbers and cannot contain a comma, so a plain separator is safe. If values could be arbitrary strings, you would need length prefixing instead.

Build left before right, matching the order they were written.

Trace ​

Serialising the example tree:

1, 2, #, #, 3, 4, #, #, 5, #, #

Reading it back:

  • build() grabs 1 \rightarrow makes node 1. Calls build() for left.
  • build() grabs 2 \rightarrow makes node 2. Calls build() for left.
  • build() grabs # \rightarrow returns None. 2.left = None. Calls build() for right.
  • build() grabs # \rightarrow returns None. 2.right = None.
  • Return to node 1. 1.left is finished. Calls build() for 1.right.
  • build() grabs 3 \rightarrow makes node 3. Calls build() for left.
  • build() grabs 4 \rightarrow makes node 4. Left #, right #. Returns 4. 3.left = 4.
  • build() grabs 5 \rightarrow makes node 5. Left #, right #. Returns 5. 3.right = 5.
  • Done, and the input is exactly consumed.

Complexity ​

  • Time Complexity: O(n) for both serialization and deserialization. We visit each of the n nodes exactly once. For serialization, we also visit n+1 null pointers. The .join() and .split() operations take time proportional to the length of the string, which is O(n). Thus, time is strictly linear.
  • Space Complexity: O(n).
    • Serialization uses an array parts of size 2n + 1 (which is O(n)). The call stack takes O(h) space.
    • Deserialization splits the string into an array of 2n + 1 tokens (O(n)) and also uses O(h) space on the call stack. Overall space is dominated by O(n).

Edge cases ​

  • Empty tree. Serialises to "#", which deserialises back to None.
  • Negative values. "-5" is one piece, and int("-5") is −5. The comma separator keeps the minus sign with its number.
  • A tree shaped like a line. Works, but the recursion is n calls deep. For very deep trees, the breadth-first version below avoids that.

The BFS alternative ​

You can serialise level by level instead, which is what LeetCode's own display format does:

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

Deserialising uses a queue: take a node off, read the next two tokens as its children, and push any non-null children back on.

It is equally valid and produces a more human-readable string. Pre-order is usually easier to write under pressure because the encoder and decoder are mirror images, while the BFS version needs a queue on both sides.

Where this goes next ​

  • Serialize and Deserialize BST (LeetCode 449) — a search tree needs no null markers at all, because the ordering already tells the decoder where each subtree ends. That produces a shorter string, and noticing why is a good test of whether you understand what the markers are for.
  • Find Duplicate Subtrees — serialise every subtree and count identical strings in a hash map.
  • Real systems — JSON, Protocol Buffers, and Python's pickle all face this problem, and all of them solve it with self-description: either explicit markers or length prefixes. Chapter 10.4 covers serialisation formats properly.

The rule: a traversal plus explicit null markers determines a tree uniquely. Self-describing data needs no second traversal.

What the interviewer will push on ​

"Why is one traversal enough here when 4.14.13 needed two?" The null markers remove the ambiguity.

"Why pre-order and not in-order?" The decoder must know the root before it can build the subtrees.

"Why the separator?" Multi-digit values would run together.

"What if node values were arbitrary strings?" Delimiters stop being safe, so length-prefix each value, exactly as in 4.4.6.

"How much bigger is the string than the tree?" 2n + 1 tokens, since a tree with n nodes has n+1 empty child slots.

"Could you do it without null markers?" For a BST, yes — the ordering substitutes for them.

One thing to volunteer: say why the naive traversal is ambiguous, with the two-node example, before you propose the fix. The fix only sounds clever when the problem it solves has been named.

Next: 4.15 is short and specific — three problems built on the trie from Chapter 4.13.4, and one of them is where backtracking and tries meet.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet