Start learning free

LESSON 492 OF 671 · BINARY TREES

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

Practice O(n) Read the full explanation

To save a binary tree in a file, you first turn it into text. This is called serializing the tree. Building the same tree back from the text is deserializing it.

Write the class Codec with two methods:

  • serialize(root) gets the root of a binary tree and returns a string. The tree may be empty.
  • deserialize(data) gets a string that serialize returned. It returns the root of the same tree, with the same shape and values.

You decide what the string looks like. Each test serializes with one Codec object and deserializes with another. So everything must be inside the string.

The tests print the rebuilt tree row by row from the top. Each row goes left to right. A missing child is written as null. The nulls at the end are left out. The examples write trees the same way.

Your starter code spells the class and method names the way your language does.

 

Example 1:

Input: root = [6,2,9,null,4,7]
Output: [6,2,9,null,4,7]
       6
      / \
     /   \
    2     9
     \   /
      4 7

Explanation: The rebuilt tree is the same as the input.
One string that works lists the nodes in preorder.
It writes # for each missing child:
"6,2,#,4,#,#,9,7,#,#,#"

Example 2:

Input: root = []
Output: []
Explanation: An empty tree needs a string too.
With the format above, that string is "#".
It must turn back into an empty tree.

Example 3:

Input: root = [-15,300]
Output: [-15,300]
  -15
  /
300

Explanation: A value can have a minus sign and several digits.
So the string needs a separator between values:
"-15,300,#,#,#"
This reads back as -15 and 300, not as single characters.

 

Constraints:

  • The tree has 0 to 200,000 nodes.
  • Each value is a whole number from -1,000 to 1,000.
  • 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
    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

    1. Start the list of pieces in serialize as this.values = [].
    2. Call the helper this.write(root). It appends the whole tree's pieces in preorder.
    3. Return this.values.join(','), the pieces glued into one string with commas between them.
    4. Declare the helper write(node).
    5. Missing child: if node is null, push '#'.
    6. Return right after, since an empty child has nothing under it.
    7. Write the node: push String(node.val).
    8. Left subtree: call this.write(node.left).
    9. Right subtree: call this.write(node.right).
    10. In deserialize, cut the string into pieces with data.split(',') and store the array in this.values.
    11. Start the position at this.pos = 0.
    12. Return this.read(), which reads the whole tree starting at piece this.pos.
    13. Declare the helper read().
    14. Take the next piece into value and advance this.pos.
    15. Empty subtree: if value is '#', return null.
    16. Real node: otherwise create new TreeNode(Number(value)). The pieces are strings, so Number turns "-1" back into the number -1.
    17. Left child: node.left = this.read().
    18. Right child: node.right = this.read().
    19. 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 JavaScript650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free