cf.completefrontend
TREES & TRIES · CORE

Tree serialization

Turn a tree into a flat string, with markers for missing children, so it can be saved and rebuilt exactly.

Time O(n)Space O(n)4 practice problemsStep-through picture

The idea

Serializing means turning a structure in memory into text, so you can store it or send it over the network. Deserializing turns the text back into the same structure. JSON.stringify and JSON.parse do this for plain objects.

For a tree, the values alone are not enough, because many shapes have the same values. The fix is to also write down where children are missing. Here we write a preorder walk (node, then left, then right), and write # every time we reach a null child.

With those markers, the text describes exactly one tree. To read it back, take the items in the same order: each item is either # (an empty spot) or a value, followed by its left subtree and then its right subtree.

An everyday example

Packing a mobile into a box

You take down a hanging mobile to ship it. You write instructions as you unhook pieces: "star, then on its left a moon, and the moon's left hook is empty, its right hook is empty, then on the star's right ...". You write "empty" for every unused hook. The person receiving it reads your list in the same order and hangs every piece on the right hook.

How the example maps to the code
In the exampleIn the code
Writing down a pieceparts.push(String(node.val))
Writing "empty" for an unused hookparts.push("#")
The instruction sheetparts.join(",")
Reading the next instructionparts[next], then next++
Hanging a piece and then its hooksnode.left = read(); node.right = read();

From the slow way to tree serialization

  1. You want to save a tree as text and load it back later. Writing just the values in preorder fails: 6 with a left child 1 and 6 with a right child 1 both come out as 6,1. The values alone drop the shape.
  2. What's missing is where each subtree ends. A tree with n nodes has exactly n + 1 empty child slots. If you write a marker, #, for each of them, a reader can tell "this subtree stops here" without any other hint.
  3. Now the text follows a simple pattern: a subtree is either #, or a value followed by two subtrees. Writing it is a preorder DFS that writes # at every null. Reading it is the same DFS run on the text: take the next item, return null if it's #, and otherwise make a node and read its left and right subtrees.
  4. The writer and the reader share one thing, the order of the items, and nothing else: no lengths, no brackets, no positions. A preorder walk that writes markers for empty spots, plus a reader that takes items in the same order with a moving index next, is tree serialization.

How it works

  1. To serialize, walk the tree in preorder with write(node).
  2. At a null child, push # into parts and return.
  3. Otherwise push the node's value, then write(node.left) and write(node.right).
  4. Join parts with commas.
  5. To deserialize, split the text on commas and read the parts with a moving index next.
  6. read() takes the next part. # means null. Otherwise make a node, then read() its left child and read() its right child, in that order.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function serialize(root) {
  2. const parts = [];
  3. function write(node) {
  4. if (node === null) {
  5. parts.push("#");
  6. return;
  7. }
  8. parts.push(String(node.val));
  9. write(node.left);
  10. write(node.right);
  11. }
  12. write(root);
  13. return parts.join(",");
  14. }
  16. function deserialize(text) {
  17. const parts = text.split(",");
  18. let next = 0;
  19. function read() {
  20. const part = parts[next];
  21. next++;
  22. if (part === "#") return null;
  23. const node = new TreeNode(Number(part));
  24. node.left = read();
  25. node.right = read();
  26. return node;
  27. }
  28. return read();
  29. }

How fast it is

TimeO(n)
Extra memoryO(n)

Every node and every empty spot is written and read once, and there are 2n + 1 of them. The text is O(n) long, and the recursion goes O(h) deep.

  • Best caseO(n)

    Any tree: every node and every empty slot must be written and read, 2n + 1 items in all.

  • Average caseO(n)

    A random tree of n nodes: n values and n + 1 markers.

  • Worst caseO(n)

    A chain of n nodes: the same 2n + 1 items, but the recursion goes n deep in both directions.

Common mistakes

  • Leaving out the markers for missing children. 1,2,3 could be several different trees, so it can't be read back.
  • Reading the right subtree before the left one. The reader must use the same order as the writer.
  • Forgetting to turn the text back into numbers with Number(part). The tree then holds strings like "4".
  • Using a separator that can appear inside values, like a comma inside a label. Pick a safe separator or escape the values.

When to use it

Look for these clues in a problem:

  • You must save a tree to a string (local storage, a URL, a file) and rebuild it later.
  • You need to compare subtrees by shape and values, for example to find duplicates.
  • The question gives a text format for nested data and asks you to parse it.
  • A tree must be sent between a worker, a server, and the page.

Check yourself

Answer each one in your head first, then open it.

How many items does the text have for a tree with n nodes?

2n + 1: n values and n + 1 markers.

Why doesn't read need to know where the left subtree ends before reading the right one?

Reading the left subtree uses up exactly its items and leaves next at the start of the right subtree, so the right call just continues from there.

What does serialize write for a single node holding 7?

7,#,#: the value followed by two markers for its empty children.

Why does preorder without markers fail for general trees?

Different shapes can give the same values in the same order, so the reader has no way to know where a subtree ends.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The text pattern: a subtree's text is # when it's empty, or value,left,right otherwise, where left and right are subtree texts too. write produces exactly this, because it writes # at null and value, then left, then right for a real node.

The rule for read: when it's called, parts[next] is the first item of some subtree's text, and when it returns, next points just past the end of that text. For # it reads one item, which is the whole text of an empty subtree. For a value it reads one item and then, by the same rule, the whole left text and the whole right text, so it stops exactly at the end.

Because read takes items in the same order write produced them, each value lands in the same place it came from, so the rebuilt tree has the same values and the same shape. It ends because every call uses at least one item, and there are 2n + 1 items.

Going deeper

3 more ideas

Why the markers make the text exact

With a # for every missing child, each node in the text is followed by exactly two descriptions: its left subtree and its right subtree. A description is either a single # or a value followed by its own two descriptions. So the reader always knows where one subtree ends, and there is only one way to read the text.

Level order works too

The format used by tests on this site writes the tree level by level with null for gaps, like [1, 2, 3, null, null, 4, 5]. It is read with a queue: each node in the queue takes the next two items as its children. Both formats work; preorder with markers is the simplest to write recursively.

Time and memory

Both directions handle every node and every missing child once. A tree with n nodes has n + 1 missing children, so the text has 2n + 1 items and the work is O(n). Memory is O(n) for the text plus O(h) for the recursion.

Work it by hand

Every step in a table, with why

Read back the text written for a 4-node tree. Every item is shown, so you can see each # close a subtree.

text = "6,1,#,3,#,#,9,#,#" (written by `serialize` for the tree `[6, 1, 9, null, 3]`)

StepnextpartResultWhat happensWhy
106new node 6read its left subtreeThe first item is always the root. Before returning, 6 must read its left subtree and then its right one.
211new node 1becomes 6.leftThe left subtree of 6 starts here. 1 now reads its own two subtrees.
32#null1.left = nullA marker: 1 has no left child. This call used exactly one item.
433new node 3becomes 1.rightThe right subtree of 1 starts with 3.
54#null3.left = null3 has no left child.
65#null3.right = null3 has no right child, so 3 is done, which finishes 1's right side, so 1 is done too.
769new node 9becomes 6.rightnext now points just past 6's whole left subtree, so this item starts the right subtree.
87#null9.left = null9 has no left child.
98#null9.right = null9 is done, so 6 is done, and the first call returns the finished tree.

The tree [6, 1, 9, null, 3], the same one that was written. The text had 9 items, 2 · 4 + 1 for 4 nodes, and next ends at 9, exactly the number of items, so nothing was skipped or left over.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Tree serializationO(n)O(n)You need a compact string that reads back into exactly the same tree.
Level order with null gapsO(n)O(n)Trees may be very deep, or you want the format often used in tests and examples.
JSON.stringify of the nodesO(n)O(n)Quick saving of small plain trees, where size and depth don't matter.

Extra memory: O(n) for the text and the parts array, plus O(h) for the recursion: about log₂ n calls deep for a balanced tree and n for a chain.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Tree serialization and the other approaches, on a scale where each line up is 10 times more steps.
  • Tree serialization, Level order with null gaps, JSON.stringify of the nodes O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Tree serialization101,0001 million
Level order with null gaps101,0001 million
JSON.stringify of the nodes101,0001 million

Inputs that need care

5 tricky inputs
An empty tree: root = null
serialize returns "#", and deserialize("#") reads that one item and returns null.
Negative and decimal values, like -4 or 2.5
String(-4) is "-4" and Number("-4") is -4, so they come back unchanged. Commas are safe, because the text of a number never contains one.
String values that contain a comma or are "#"
split(",") would cut such a value in two, and a value "#" would read as an empty spot. Escape these, or encode each value with JSON.stringify.
The value -0
String(-0) is "0", so -0 comes back as 0. That's usually harmless; if it matters, write a special marker for it.
A chain 30,000 nodes deep
Both functions recurse 30,000 calls deep and may overflow the stack. Use the level-order format with a queue, which needs no recursion.

Variations and follow-ups

Twists interviewers add

Level-order format

Write the tree level by level with a queue, null for gaps, and drop the trailing nulls, as in [6, 1, 9, null, 3]. Reading uses a queue too: each node takes the next two items as its children. It never recurses, so depth is no problem.

Search trees without markers

A BST's preorder alone is enough, because the order rule decides where each value goes. Read it back with bounds, as when building a BST from preorder. The text is about half as long.

Trees with many children

Write each node's value followed by its number of children, like 1,3,..., then each child's text. The count does the job of the markers.

JSON

JSON.stringify(root) works directly for small trees of plain objects, since null children become null. The text is larger, the work is recursive, and it throws on cycles, such as nodes that also store a parent pointer.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "serialize", "encode and decode", "save and restore a tree", or "send a tree over the network".
  • Show why the markers matter with two tiny trees: 6 with a left child 1 writes 6,1,#,#,#, while 6 with a right child 1 writes 6,#,1,#,#.
  • Say that the writer and the reader must walk in the same order, and point at next as the only shared state the reader needs.
  • Expect "can you make it shorter?". For a BST, drop the markers and use preorder alone. For other trees, drop the trailing markers in the level-order form.

Where frontend code uses it

The same idea in real UI code
  • Saving an editor's split-pane layout or a tree view's open folders to localStorage means serializing a tree and parsing it back on the next visit.
  • element.outerHTML serializes a DOM subtree into HTML text, and DOMParser turns HTML text back into a DOM tree.
  • Server-side rendering turns a component tree into an HTML string on the server, and the browser parses it back into the DOM.

Related algorithms