Start learning free

LESSON 422 OF 540 · BINARY TREES

Serialize and Deserialize a Binary Tree in Scala: Preorder in 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

    SCALA · BINARY TREES

    Serialize And Deserialize Binary Tree in Scala, explained

    Problem overview

    The class Codec has two methods. serialize(root) takes the root of a binary tree, which may be empty (null), and returns 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: new TreeNode(value) makes a node, and its left and right fields start as null.

    The tests serialize a tree with one Codec, rebuild it with a second Codec, and print the result level by level. So the string must carry everything the rebuilding needs. Nothing is shared between the two objects except that string.

    Approach: preorder with a marker for every missing child

    Listing the values alone isn't enough: many different trees have the same values in the same order. The fix is to write the tree in preorder (a node, then its left subtree, then its right subtree) and to write a marker, here #, for every missing child. The root 1 with children 2 and 3 becomes 1,2,#,#,3,#,#.

    The markers tell the reader exactly where each subtree ends. Reading the pieces from left to right, a number starts a node whose left subtree follows immediately, then its right subtree. A # is a complete, empty subtree. The empty tree is the string #.

    Commas separate the pieces, so values with several digits or a minus sign, like -100, come back whole. Both methods visit each node once, so both run in O(n).

    For the first example, [1,2,3,null,null,4,5], the code produces 1,2,#,#,3,4,#,#,5,#,#, and reading it back gives the same tree.

    Step by step

    1. Declare the shared list. A field var values holds the pieces as an scala.collection.mutable.ArrayBuffer[String](). Fields are visible to every method, so the helpers can add to the list and read from it.
    2. Start fresh in serialize. Assign a new, empty buffer to values, so each call builds its own list.
    3. Call the helper write(root), which adds the pieces of the whole tree in preorder.
    4. Glue the pieces: values.mkString(",") puts a comma between each two.
    5. Write write(node: TreeNode): Unit. It adds the pieces of the subtree under node.
    6. Missing child. If node is null, add "#" with +=.
    7. Return early after the marker, since an empty child has nothing under it.
    8. Add the node. Add node.value.toString. The node comes first, which is what makes it preorder.
    9. Left subtree. Call write(node.left).
    10. Right subtree. Call write(node.right).
    11. Add the reader's position. A second field, var pos = 0, is the index of the next piece deserialize will read.
    12. Cut the string. In deserialize, data.split(",") gives an array of pieces, and ArrayBuffer.from(...) turns it into an ArrayBuffer stored in values.
    13. Reset pos to 0 and return what read() gives: one whole subtree starting at pos, which here is the whole tree.
    14. Write read(): TreeNode, the mirror of write. It takes the piece at pos into value and moves pos forward.
    15. Empty subtree. If value is "#", return null.
    16. Real node. Otherwise create new TreeNode(value.toInt).
    17. Children. Set node.left to read(), then node.right to read(). The first call consumes all the pieces of the left subtree and stops where the right one begins.
    18. Return the node.

    The solution in Scala

    class Codec {
    var values = scala.collection.mutable.ArrayBuffer[String]()
    var pos = 0

    def write(node: TreeNode): Unit = {
        if (node == null) {
            values += "#"
            return
        }
        values += node.value.toString
        write(node.left)
        write(node.right)
    }

    def serialize(root: TreeNode): String = {
        values = scala.collection.mutable.ArrayBuffer[String]()
        write(root)
        return values.mkString(",")
    }

    def read(): TreeNode = {
        val value = values(pos)
        pos += 1
        if (value == "#") {
            return null
        }
        val node = new TreeNode(value.toInt)
        node.left = read()
        node.right = read()
        return node
    }

    def deserialize(data: String): TreeNode = {
        values = scala.collection.mutable.ArrayBuffer.from(data.split(","))
        pos = 0
        return read()
    }
}

    Scala details worth knowing:

    • += on a buffer. values += "#" appends to an ArrayBuffer in place. It works on values even though the field is a var, because the buffer is a mutable collection and += calls its append method.
    • var versus val. values is a var because serialize and deserialize each replace the whole buffer. pos is a var because it counts upward.
    • split returns an Array[String]. For "1,2,#" the pieces are 1, 2 and #, and for "#" it is the single piece #. ArrayBuffer.from copies them into a buffer, which is the type of values.
    • Converting numbers. node.value.toString writes an Int as text, and value.toInt reads it back, including negative numbers such as "-100".
    • Comparing strings. value == "#" compares contents in Scala, so no special method is needed.
    • Unit. write returns Unit, Scala's "no useful result". The bare return in it leaves the method early.
    • State between calls. deserialize sets values and pos itself every time, so the same Codec can serialize and deserialize repeatedly, and a second Codec can read a string it didn't write.

    Complexity

    Time: O(n) for each method, where n is the number of nodes. A tree with n nodes has n + 1 empty children, so the string has 2n + 1 pieces. write and read each handle one piece per call, and mkString and split go through the pieces once.

    Space: O(n). The list of pieces and the string both grow with the tree, and the recursion is as deep as the tree is tall (at most 400 levels in this lesson).

    Edge cases and common mistakes

    • The empty tree. serialize(null) gives "#", and deserialize("#") gives null. Returning an empty string would break deserialize: split on an empty string gives one empty piece, and converting it with toInt throws a NumberFormatException.
    • Leaving out the markers. The values [1,2] could then be a left child or a right child. Writing every missing child removes that doubt: [1,2] with 2 on the left is 1,2,#,#,#, and with 2 on the right it is 1,#,2,#,#.
    • No separator. Without commas, the pieces 1, 0 and # would run together as 10#, which could equally be the number 10 followed by a marker. The commas keep every value whole.
    • Reading pieces out of order. read must take the left subtree before the right one, in the same order write used. Swapping them in only one of the methods mirrors the tree.
    • Forgetting to advance pos. If read doesn't move pos on every piece, including #, it reads the same piece again and never finishes.

    Testing

    Each row shows the string produced by serialize and the tree that a second Codec rebuilt from it, printed level by level:

    TreeSerialized stringRebuilt 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,null,2,null,3]1,#,2,#,3,#,#[1,null,2,null,3]
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free