Start learning free

LESSON 422 OF 540 · BINARY TREES

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

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 * 105].
  • 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 21
    Ctrl + Enter to check

    TYPESCRIPT · BINARY TREES

    Serialize And Deserialize Binary Tree in TypeScript, explained

    Problem overview

    The class Codec has two methods. serialize(root) takes the root of a binary tree, which may be empty, and returns a string. deserialize(data) takes a string made by serialize and returns the root of the same tree: the same shape and the same value in every node. The format of the string is up to you, as long as the two methods agree on it.

    The lesson provides the TreeNode class, with val, left and right; its constructor takes the value and starts both children as null. The tests serialize a tree with one Codec, rebuild it with a different Codec, and print the result in level order.

    For the tree [1,2,3,null,null,4,5], the solution's string is 1,2,#,#,3,4,#,#,5,#,#. For the empty tree it is #. For [-1,0,null,null,-100] it is -1,0,#,-100,#,#,#.

    Approach: preorder with markers for missing children

    A list of node values alone can't be turned back into a tree, because many shapes share the same values. The fix is to also write down where the tree is empty. We walk the tree in preorder (a node, its left subtree, its right subtree) and write # for every missing child.

    With those markers, the string says exactly where each subtree ends, so reading it back is unambiguous. To rebuild, read one piece. A # is an empty subtree. A number is a node, and the pieces that follow are first its entire left subtree and then its entire right subtree, so the same routine can be called twice for the children. The reading pointer moves forward once per piece, so each direction is O(n).

    The pieces are separated by commas. Without separators, -100 and a run of values like 12 would be ambiguous; with them, each value is read whole, minus sign included.

    Step by step

    Serialize

    1. State. The class keeps values, a string[] that starts empty, as a property, so the helpers can add to it and read from it.
    2. Fresh list. serialize sets this.values = [] so each call starts from scratch.
    3. Walk the tree. It calls the helper this.write(root), which adds the pieces of the whole tree in preorder.
    4. Join. this.values.join(',') glues the pieces into one string with commas between them.
    5. The helper write. If node === null, push '#' and return: an empty child has nothing below it.
    6. A real node. Push String(node.val) first (preorder), then call this.write(node.left), then this.write(node.right).

    Deserialize

    1. A second property. pos, a number starting at 0, is the position of the next piece to read.
    2. Cut the string. data.split(',') gives the pieces back, in the order they were written, and goes into this.values.
    3. Reset the position to 0, then return what this.read() gives: it reads one whole subtree, and called first it reads the whole tree.
    4. The helper read. Take this.values[this.pos] into value and move this.pos forward.
    5. Empty child. If value === '#', return null.
    6. A real node. Create new TreeNode(Number(value)). Set node.left to this.read() and then node.right to this.read(). The first call consumes every piece of the left subtree, # markers included, and leaves the position at the start of the right subtree. Return the node.

    The solution in TypeScript

    class Codec {
    values: string[] = [];
    pos: number = 0;

    write(node: TreeNode | null): void {
        if (node === null) {
            this.values.push('#');
            return;
        }
        this.values.push(String(node.val));
        this.write(node.left);
        this.write(node.right);
    }

    serialize(root: TreeNode | null): string {
        this.values = [];
        this.write(root);
        return this.values.join(',');
    }

    read(): TreeNode | null {
        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: string): TreeNode | null {
        this.values = data.split(',');
        this.pos = 0;
        return this.read();
    }
}

    TypeScript details

    • String(node.val) and Number(value) are real conversions that happen at run time. A cast such as value as number would convert nothing, because types are erased when the code compiles to JavaScript. Number('#') would give NaN, which is why the marker is checked first.
    • join(',') and split(',') are inverses here. Negative numbers survive the trip: String(-100) is '-100' and Number('-100') is -100.
    • Comparing with === against null and '#' avoids the loose-equality surprises of ==.
    • The empty tree is not special. serialize(null) pushes one marker and returns #, and deserialize('#') reads that marker and returns null. Note that ''.split(',') gives [''], not an empty array, so an empty string would not be a valid encoding of the empty tree here.

    Complexity

    Time: O(n) for both methods. A tree with n nodes has n + 1 empty children, so the string has 2n + 1 pieces. Each piece is written once and read once, with constant work per piece, and join and split are linear in the size of the string.

    Space: O(n) for the list of pieces and the string, plus recursion depth equal to the tree's height (at most 400 here).

    Edge cases and common mistakes

    • Leaving out the # markers. Values alone don't fix the shape: the trees [1,2] and [1,null,2] have the same preorder values and different shapes.
    • No separator. Without commas, -1,0 and -10 could not be told apart. The comma also makes multi-digit and negative values safe.
    • Reading the right side first. read must take the left subtree before the right one, in the same order write used.
    • Forgetting to reset. deserialize sets pos to 0 each time, and serialize clears values each time. Because of that, one Codec can serialize and deserialize several trees in a row.
    • The empty tree. It must produce a non-empty string, #.

    Testing

    Serializing with one Codec, rebuilding with a second one, and printing the rebuilt tree in level order gives:

    TreeStringRebuilt tree
    [1,2,3,null,null,4,5]1,2,#,#,3,4,#,#,5,#,#[1,2,3,null,null,4,5]
    []#[]
    [-1,0,null,null,-100]-1,0,#,-100,#,#,#[-1,0,null,null,-100]
    [5]5,#,#[5]
    [1,null,2,null,3]1,#,2,#,3,#,#[1,null,2,null,3]
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free