Start learning free

LESSON 418 OF 536 · BINARY TREES

Serialize and Deserialize Binary Tree in Java: 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 21

Guided

Ctrl + Enter to check

JAVA · BINARY TREES

Serialize And Deserialize Binary Tree in Java, 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 made by serialize and returns the root of the same tree, with the same shape and the same value in every node. The format of the string is up to you. The lesson provides the TreeNode class, with val, left, right and a constructor that takes the value.

The tests serialize a tree with one Codec object and rebuild it with a second one. So deserialize can rely on nothing but the string: whatever the first object remembered in its fields is gone.

For the tree with root 1, children 2 and 3, and 4 and 5 below 3, the tests write it level by level as [1,2,3,null,null,4,5]. The solution below turns it into 1,2,#,#,3,4,#,#,5,#,#.

Approach: preorder with markers for missing children

A list of node values is not enough to rebuild a tree: 1,2 could be a root with a left child or a root with a right child. The fix is to record the empty spots too. The format here writes the tree in preorder (a node, then its left subtree, then its right subtree) and writes # for every missing child, with commas between the pieces.

The # markers make the string self-delimiting. When reading, a number means "a node starts here", and the very next pieces are its left subtree, which ends exactly when the reading of that subtree is complete. Then come the pieces of the right subtree. A # is a complete subtree by itself, the empty one. Reading follows the same recursion as writing, in the same order, so it needs no lengths and no brackets.

The commas matter because values can have several digits and a minus sign. Without them, -1 followed by 0 would look like a different number.

The empty tree is just #, and reading it gives null. Each node and each marker is written once and read once, so both methods take O(n) time.

Step by step

Declare the list of pieces as a field, values, a List<String>. Both methods use it, and so do their helpers.
In serialize, start values as a new ArrayList, so each call begins from scratch.
Call the helper write(root), which adds the pieces of the whole tree in preorder.
Join the pieces with String.join(",", values) and return the result.
Declare write(TreeNode node), which adds the pieces of the subtree under node.
Write "#" for a null node.
Return right after the marker. An empty child has nothing below it, and the rest of the method is for real nodes.
Add the node's value as a string with String.valueOf(node.val). The node comes first because this is preorder.
Write the left subtree with write(node.left).
Write the right subtree with write(node.right).
Add the second field, pos, the position of the next piece deserialize will read.
In deserialize, cut the string into pieces with data.split(",") and store them in values. Arrays.asList turns the resulting array into a List.
Start pos at 0, the first piece.
Return what read() gives. It reads one whole subtree starting at pos, which here is the whole tree.
Declare TreeNode read(), which mirrors write.
Take the next piece with values.get(pos) and move pos forward by one.
Return null for #, using value.equals("#").
Otherwise create a node holding Integer.parseInt(value). A leading minus sign is part of the piece, so negative values come back whole.
Set node.left to read(). That call consumes every piece of the left subtree, markers included, and stops where the right subtree begins.
Set node.right to read(). Now pos is just past this node's whole subtree.
Return the node.

The solution in Java

class Codec {
    List<String> values;
    int pos;

    void write(TreeNode node) {
        if (node == null) {
            values.add("#");
            return;
        }
        values.add(String.valueOf(node.val));
        write(node.left);
        write(node.right);
    }

    public String serialize(TreeNode root) {
        values = new ArrayList<>();
        write(root);
        return String.join(",", values);
    }

    TreeNode read() {
        String value = values.get(pos);
        pos++;
        if (value.equals("#")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(value));
        node.left = read();
        node.right = read();
        return node;
    }

    public TreeNode deserialize(String data) {
        values = Arrays.asList(data.split(","));
        pos = 0;
        return read();
    }
}

Here are real round trips through two separate Codec objects, each shown as the tree, the string, and the rebuilt 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]
[7] -> "7,#,#" -> [7]
[1,2,null,3] -> "1,2,3,#,#,#,#" -> [1,2,null,3]

Java details worth a closer look:

String.join. It glues the strings of any Iterable with the given separator. For a single piece, such as "#", there is no comma at all. Building the result by repeated + on a String would copy the text again each time and be slow for 200,000 nodes.
split(","). It returns an array of the pieces between the commas. The string "#" gives the one-element array ["#"]. The argument is a regular expression, and a comma is not special in one.
Arrays.asList returns a fixed-size list backed by the array. It supports get, which is all read does, but adding to it throws UnsupportedOperationException. That is why serialize creates a real ArrayList instead.
Strings compare with equals. value.equals("#") compares the characters. value == "#" would compare references and can be false for a piece that was cut out of the data string.
pos and values are fields. read changes pos, and the change is seen by every recursive call. That is what lets the left call move the position past its subtree before the right call starts.
Parsing. Integer.parseInt("-100") returns -100. Values in this lesson are between -1000 and 1000, so a # can never be confused with a number.

Complexity

Time: O(n) for both methods. write is called once for each of the n nodes and once for each of the n + 1 missing children, and each call adds one piece. String.join and split each make a single pass over the text. read is called once per piece.

Space: O(n). The list holds 2n + 1 pieces and the string is about as long as all of them together. The recursion goes as deep as the tree, at most 400 levels here.

Edge cases and common mistakes

The empty tree. serialize(null) returns "#", and deserialize("#") returns null. Without a marker for it, serialize would return an empty string, and "".split(",") gives an array holding one empty string, which parseInt rejects.
Skipping the markers. A preorder list with only values describes many different trees. Every missing child needs its #.
No separator. Joining with "" makes negative and multi-digit values ambiguous.
Depending on the first object. Because the tests deserialize with a different Codec, a solution that keeps the tree, or a list of nodes, in a field of the serializer passes a one-object test and fails here. deserialize rebuilds values and pos from the string alone.
Not resetting pos. A second call of deserialize on the same object would start in the middle of the old data. The solution sets pos = 0 each time.
Reading the right child before the left. The two reads in read are in the order the pieces were written. Swapping them mirrors the tree.

Testing

[1,2,3,null,null,4,5] serializes to 1,2,#,#,3,4,#,#,5,#,# and comes back as the same tree.
[] serializes to # and comes back as the empty tree.
[-1,0,null,null,-100] serializes to -1,0,#,-100,#,#,# and comes back unchanged.
[7] serializes to 7,#,#.
[1,2,null,3] serializes to 1,2,3,#,#,#,# and comes back unchanged.

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

Start learning free