Tree Algorithms

Serialize and Deserialize a Tree

What is Serialization?

Serialization converts a tree into a flat string (or byte stream) that can be saved to disk, sent over a network, or stored in a database. Deserialization is the reverse: reading that string back and rebuilding a tree that's structurally identical to the original — same shape, same values, same left/right placement everywhere.

How Does It Work?

The tricky part isn't encoding the values — it's encoding the *shape*. A plain list of values loses information about which nodes were children of which, and where branches were missing. The standard fix is to explicitly record empty children with a marker (commonly "null" or "#") at every point a node is absent, using a preorder traversal: visit the node, then recurse left, then recurse right, writing a marker whenever a child doesn't exist.

Because every empty spot is explicitly recorded, deserialization can rebuild the exact structure by reading tokens in that same preorder sequence: read one token — if it's a null marker, that subtree is empty; otherwise create a node from it, then recursively build its left child from the next tokens, then its right child. The reader never needs to guess where one subtree ends and another begins.

Preorder with null markers: visit 8, then 3, then 1 (both children null), back up, 6 (both children null), back up, 10 (both children null)

Algorithm Steps

Serialize (preorder, with null markers):
- If the current node is empty, write a null marker and return
- Otherwise, write the node's value
- Recurse into the left child, then the right child
Deserialize (read tokens in the same order they were written):
- Read the next token
- If it's a null marker, this subtree is empty — return immediately
- Otherwise, create a node from it, then recursively read its left child, then its right child

Time Complexity

Time Complexity: O(n) for both serialize and deserialize — every node and every null marker is visited exactly once.
Space Complexity: O(n) for the output string, plus O(h) recursion stack for the traversal.

Time Complexity Analysis

This pattern shows up anywhere tree-shaped data needs to survive outside memory: saving a game's scene graph, sending a parsed expression tree between services, caching a computed index structure, or simply persisting any hierarchical data model to JSON or a file.

Daily DSA Challenge by Scale Engineer

Encode a tree into a string, then rebuild it back into an identical tree

Build a tree, then serialize it

Source Tree

No tree yet — insert a value or generate a random tree

Reconstructed Tree

Deserialize a string to rebuild a tree here

Internal nodeLeaf nodeRootVisited during serializeCreated during deserialize

Test Your Knowledge before moving forward!

Serialize & Deserialize Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Serialize and Deserialize Implementation

// Binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Preorder traversal, writing a "null" marker for every empty child so the
// shape of the tree — not just its values — is fully recoverable.
function serialize(root) {
  const tokens = [];

  function visit(node) {
    if (node === null) {
      tokens.push("null");
      return;
    }
    tokens.push(String(node.value));
    visit(node.left);
    visit(node.right);
  }

  visit(root);
  return tokens.join(",");
}

// Reads tokens in the same preorder sequence they were written in.
function deserialize(data) {
  const tokens = data.split(",");
  let i = 0;

  function build() {
    const token = tokens[i++];
    if (token === "null") return null;

    const node = new TreeNode(Number(token));
    node.left = build();
    node.right = build();
    return node;
  }

  return build();
}

// Usage example
const encoded = serialize(root);          // "8,3,1,null,null,6,null,null,10,null,null"
const rebuilt = deserialize(encoded);      // structurally identical tree

Done With the Learning

Mark Serialize/Deserialize as done and view it on your dashboard

Explore Other Tree Topics

Tree Diameter

Tree Isomorphism

Lowest Common Ancestor

Level-order Traversal

Structure & Properties