Start learning free

LESSON 418 OF 536 · BINARY TREES

Serialize and Deserialize a Binary Tree in JavaScript: O(n) Preorder

Practice O(n) Read the full explanation

Serializing a tree turns it into a string, so it can be saved in a file or sent over a network. Deserializing rebuilds the same tree from that string.

Implement the class Codec:

serialize(root) gets the root of a binary tree, which may be empty, and returns a string.
deserialize(data) gets a string made by serialize and returns the root of the same tree: the same shape, with the same value in every node.

The string's format is up to you. The tests serialize each tree with one Codec, rebuild it with a second Codec's deserialize, and print the rebuilt tree level by level, from left to right, with null where a child is missing and the trailing nulls left out. The trees below are written the same way. serialize must return a string. The starter code spells these names the way your language does.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
    1
   / \
  2   3
     / \
    4   5

Explanation: One string that works lists the nodes in preorder, with # for a missing child: "1,2,#,#,3,4,#,#,5,#,#". Reading it back gives the same tree.

Example 2:

Input: root = []
Output: []
Explanation: The empty tree needs a string too, for example "#", and deserialize gives back an empty tree.

Example 3:

Input: root = [-1,0,null,null,-100]
Output: [-1,0,null,null,-100]
    -1
    /
   0
    \
   -100

Explanation: Values can be negative and have several digits. With commas between the pieces, as in "-1,0,#,-100,#,#,#", every value is read back whole.

Constraints:

The number of nodes in the tree is in the range [0, 2 * 10⁵].
Each node value is between -1000 and 1000.
The tree is at most 400 levels deep.

Note:

Both serialize and deserialize should run in O(n) time, where n is the number of nodes.

STEP 1 OF 19

Guided

Ctrl + Enter to check

JAVASCRIPT · BINARY TREES

Serialize And Deserialize Binary Tree in JavaScript, explained

Problem overview

The class Codec has two methods. serialize(root) turns a binary tree, possibly empty, into a string. deserialize(data) takes a string that serialize produced and returns the root of the same tree: the same shape and the same value in every node. The format is up to you. The lesson provides TreeNode, built as new TreeNode(val), with val, left and right fields.

The tests serialize each tree with one Codec and rebuild it with the deserialize of a second one, so the string must carry everything: deserialize can't rely on anything stored in the first object. For the tree [1,2,3,null,null,4,5] this solution writes "1,2,#,#,3,4,#,#,5,#,#", and for the empty tree it writes "#".

Approach: preorder with a marker for every missing child

A list of values alone doesn't determine a tree: the values 1, 2 could be a root with a left child or with a right child. The fix is to write the missing children too. The solution walks the tree in preorder, a node and then its left and right subtrees, and writes # wherever a child is missing. Each # is a complete, empty subtree, so the reader always knows where a subtree ends.

Reading mirrors writing. Take the next piece. If it is #, the subtree is empty. Otherwise it is a node's value: create the node, read its left subtree, then read its right subtree. Each read call consumes exactly the pieces of one subtree, so the right subtree starts exactly where the left one stopped.

The pieces are separated by commas because values can have several digits and a minus sign. Without a separator, "-100" could be read as other values. Splitting at the commas gives each value back whole.

Step by step

Start the list of pieces in serialize as this.values = [].
Call the helper this.write(root). It appends the whole tree's pieces in preorder.
Return this.values.join(','), the pieces glued into one string with commas between them.
Declare the helper write(node).
Missing child: if node is null, push '#'.
Return right after, since an empty child has nothing under it.
Write the node: push String(node.val).
Left subtree: call this.write(node.left).
Right subtree: call this.write(node.right).
In deserialize, cut the string into pieces with data.split(',') and store the array in this.values.
Start the position at this.pos = 0.
Return this.read(), which reads the whole tree starting at piece this.pos.
Declare the helper read().
Take the next piece into value and advance this.pos.
Empty subtree: if value is '#', return null.
Real node: otherwise create new TreeNode(Number(value)). The pieces are strings, so Number turns "-1" back into the number -1.
Left child: node.left = this.read().
Right child: node.right = this.read().
Return the node.

The solution in JavaScript

class Codec {
    write(node) {
        if (node === null) {
            this.values.push('#');
            return;
        }
        this.values.push(String(node.val));
        this.write(node.left);
        this.write(node.right);
    }

    serialize(root) {
        this.values = [];
        this.write(root);
        return this.values.join(',');
    }

    read() {
        let value = this.values[this.pos];
        this.pos++;
        if (value === '#') {
            return null;
        }
        let node = new TreeNode(Number(value));
        node.left = this.read();
        node.right = this.read();
        return node;
    }

    deserialize(data) {
        this.values = data.split(',');
        this.pos = 0;
        return this.read();
    }
}

Details worth knowing:

The state lives on this. values and pos are properties, so the recursive helpers share them without passing them around. serialize and deserialize each reset values first, so a Codec can be used again.
join and split are inverses here. join(',') puts a comma between pieces, and split(',') cuts at every comma. This is safe because no piece contains a comma: the pieces are integers and #.
Number and String. Values are stored as text and converted back. Number("-100") is -100, with the sign included.
=== against null. write checks node === null, which matches the null the lesson's nodes use for a missing child.

Complexity

Time: O(n) for both methods. write is called once per node plus once per missing child, which is 2n + 1 calls in all, and each does constant work. join and split are linear in the length of the string. read consumes each of the 2n + 1 pieces once.

Space: O(n). The list and the string hold about 2n + 1 pieces. The recursion is as deep as the tree, which the lesson limits to 400 levels.

Edge cases and common mistakes

The empty tree. write(null) pushes only #, so the string is "#". deserialize("#") reads that piece and returns null.
A single node. The tree [7] becomes "7,#,#".
A left chain. The tree [1,2,null,3] becomes "1,2,3,#,#,#,#", and it is different from a right chain, which has its markers in other places.
Negative and multi-digit values. [-1,0,null,null,-100] becomes "-1,0,#,-100,#,#,#" and comes back whole, thanks to the commas.
Leaving out the # markers. A preorder list of values alone can't tell where a subtree ends.
Reading the right subtree before the left. read must take the pieces in the same order write put them.
Passing pos by value. A plain number argument would not carry the progress made by the left call to the right call. A property on this does.

Testing

Trees are in level order; each result was serialized by one Codec and rebuilt by another.

[1,2,3,null,null,4,5] gives the string "1,2,#,#,3,4,#,#,5,#,#" and comes back as [1,2,3,null,null,4,5].
[] gives "#" and comes back as [].
[-1,0,null,null,-100] gives "-1,0,#,-100,#,#,#" and comes back as [-1,0,null,null,-100].
[7] gives "7,#,#" and comes back as [7].
[1,2,null,3] gives "1,2,3,#,#,#,#" and comes back as [1,2,null,3].

Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free