Start learning free

LESSON 422 OF 540 · BINARY TREES

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

    KOTLIN · BINARY TREES

    Serialize And Deserialize Binary Tree in Kotlin, explained

    Problem overview

    You implement a class Codec with 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: the same shape and the same value in every node. The format of the string is your choice.

    The lesson provides TreeNode: a class with an Int property value and two nullable properties, left and right. In the lesson's tests one Codec serializes the tree and a second, separate Codec rebuilds it. So the string has to carry everything: the second object knows nothing but data.

    For the tree [1,2,3,null,null,4,5] the solution below produces 1,2,#,#,3,4,#,#,5,#,#, and deserialize turns that back into [1,2,3,null,null,4,5].

    Approach

    A list of the values in preorder (node, left subtree, right subtree) is not enough on its own: [1,2] could be a root with a left child or a root with a right child. The fix is to write a marker, here #, for every missing child. With the markers, the end of every subtree is visible in the text, so the string describes exactly one tree.

    Reading the string back mirrors writing it. Take the next piece. If it is #, this subtree is empty. Otherwise it is a node's value: create the node, then read its left subtree, which consumes the pieces right after it, then read its right subtree. Each recursive read takes exactly the pieces of one subtree and stops where the next one begins, so a single position counter that only moves forward is all the bookkeeping needed.

    Commas separate the pieces. They matter because values have several digits and can be negative: without a separator, the pieces 1, 0, 0 and the single value 100 would look the same. With commas, every value is read back whole.

    Step by step

    Writing the string

    1. Keep the pieces. Add a property var values = mutableListOf<String>(). Both methods and both helpers use it.
    2. serialize. Start with a new empty list, call the helper write(root), and return values.joinToString(","), which glues the pieces together with a comma between each two. Resetting the list at the start means every call to serialize builds its string from scratch.
    3. The helper write(node). If node is null, add "#" and return: an empty child has nothing below it.
    4. Otherwise add node.value.toString(), then call write on node.left and on node.right, in that order. The node comes first, which is what makes it preorder.

    Reading it back

    1. Keep the position. Add a property var pos = 0: the index of the next piece to read.
    2. deserialize. Cut the string into pieces with data.split(","), convert to the same kind of list with toMutableList(), store it in values, set pos to 0 and return the result of read().
    3. The helper read(). Take values[pos] into value and move pos forward by one. If value is "#", return null.
    4. Otherwise create TreeNode(value.toInt()), set its left to read() and then its right to read(), and return the node. The order of those two lines must match the order in write.

    The solution in Kotlin

    class Codec {
    var values = mutableListOf<String>()
    var pos = 0

    fun write(node: TreeNode?) {
        if (node == null) {
            values.add("#")
            return
        }
        values.add(node.value.toString())
        write(node.left)
        write(node.right)
    }

    fun serialize(root: TreeNode?): String {
        values = mutableListOf()
        write(root)
        return values.joinToString(",")
    }

    fun read(): TreeNode? {
        val value = values[pos]
        pos++
        if (value == "#") {
            return null
        }
        val node = TreeNode(value.toInt())
        node.left = read()
        node.right = read()
        return node
    }

    fun deserialize(data: String): TreeNode? {
        values = data.split(",").toMutableList()
        pos = 0
        return read()
    }
}

    Kotlin details worth knowing

    • var properties. values is reassigned in both serialize and deserialize, and pos changes while reading, so both are var. The list type is MutableList<String>: a plain List has no add. That is why deserialize calls toMutableList() on the result of split, which returns a read-only List<String>.
    • mutableListOf() with no type. In values = mutableListOf() Kotlin infers String from the property's type, so the type argument can be left out there.
    • joinToString(","). It converts each element to text and puts the separator between elements, not after the last one. A list with the single piece "#" gives #, and an empty list gives an empty string.
    • Negative numbers. "-1".toInt() is -1, so the minus sign inside a piece needs no special care. For [-1,0,null,null,-100] the string is -1,0,#,-100,#,#,#.
    • Smart cast on the parameter. After the node == null check returns, Kotlin treats node as non-null, so node.value compiles without !!.
    • == on strings. value == "#" compares contents, as Kotlin's == always does. No equals call is needed.

    Complexity

    • Time: O(n) for both methods, where n is the number of nodes. write is called once for each node and once for each missing child, which is n + 1 empty children, so about 2n + 1 calls with O(1) work each. joinToString and split each go over a string of that size once. read consumes each piece exactly once.
    • Space: O(n) for the list of pieces and the string, plus the recursion stack, as deep as the tree is tall (the constraints keep it at 400 levels).

    Edge cases and common mistakes

    • The empty tree. write(null) adds "#", so serialize returns # and deserialize("#") returns null. Returning an empty string for an empty tree would break deserialize: the split of an empty string gives one empty piece, which is not #, and "".toInt() fails with a NumberFormatException.
    • Leaving out the markers. Without # for missing children, different trees give the same string.
    • Leaving out the commas. Values like -100 and 1000 have several characters, so the reader needs separators to cut the string at the right places.
    • Different order in the two directions. If read filled right before left while write wrote left first, the subtrees would swap places.
    • Stale state. serialize starts with a new list on purpose. Without that line, a second call on the same object would append to the old pieces and return a longer string.
    • Deep trees. A tree that is a line of 400 nodes writes 801 pieces, and the recursion goes 400 levels deep, which is fine here.

    Testing

    Each tree below was serialized by one Codec and rebuilt by another. The tree is written in level order, as the lesson's tests print it:

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