297.serialize-and-deserialize-binary-tree.md

297. Serialize and Deserialize Binary Tree

Key Insights

The challenge of this problem is that a standard tree traversal (preorder, inorder, or postorder) doesn't store enough information to uniquely reconstruct the tree's structure. For example, the preorder traversal of the following two trees is the same:

    1
   / \
  2   3

    1
   /
  2
   \
    3

To uniquely reconstruct the tree, we need to:

1. Know where the leaf nodes end. In other words, we can't skip the null node, we have to encode them explicitly.
2. Use a delimiter to distinguish between different nodes in the serialized string.

Next, we can use either DFS or BFS to serialize and deserialize the tree. The key is to ensure that we include null nodes in our serialization to capture the structure of the tree accurately.

DFS

• Serialization: We use preorder to serialize the tree. For each node, we append its value to the string, and for null nodes, we append a special character (e.g., "X"). We also use a delimiter (e.g., ",") to separate the values.

     1
   /   \
  2     3
       / \
      4   5

f(1) = "1," + f(2) + "," + f(3)
    f(2) = "2," + f(null) + "," + f(null) = "2,X,X"
    f(3) = "3," + f(4) + "," + f(5)
        f(4) = "4," + f(null) + "," + f(null) = "4,X,X"
        f(5) = "5," + f(null) + "," + f(null) = "5,X,X"

• Deserialization: We split the serialized string by the delimiter to get a list of node values. The first value is always the root. We can then recursively build the left and right subtrees by consuming the list of node values in order.

f(1,2,X,X,3,4,X,X,5,X,X)
    root = 1
    root.left = f(2,X,X,3,4,X,X,5,X,X)
        root = 2
        root.left = f(X,X,3,4,X,X,5,X,X) = null
        root.right = f(X,3,4,X,X,5,X,X) = null
    root.right = f(3,4,X,X,5,X,X)
        root = 3
        root.left = f(4,X,X,5,X,X)
            root = 4
            root.left = f(X,X,5,X,X) = null
            root.right = f(X,5,X,X) = null
        root.right = f(5,X,X)
            root = 5
            root.left = f(X,X) = null
            root.right = f(X) = null

private const val NULL = "X"
private const val DELIMITER  = ","

class Codec() {
    // Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        val str = StringBuilder()
        buildString(root, str)
        return str.toString()
    }

    private fun buildString(root: TreeNode?, str: StringBuilder) {
        if (root == null) {
            str.append(NULL)
            return
        }
        str.append(root.`val`)
        str.append(DELIMITER)
        buildString(root.left, str)
        str.append(DELIMITER)
        buildString(root.right, str)
    }

    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        if (data.isEmpty() || data == NULL) return null

        val splits = data.split(DELIMITER)
        val queue = ArrayDeque<String>()
        for (s in splits) queue.addLast(s)
        
        return buildTree(queue)
    }

    private fun buildTree(queue: ArrayDeque<String>): TreeNode? {
        if (queue.isEmpty()) return null
        val value = queue.removeFirst()
        if (value == NULL) return null
        
        val root = TreeNode(value.toInt())
        root.left = buildTree(queue)
        root.right = buildTree(queue)
        return root
    }
}

BFS

class Codec() {

    private val nullNode = TreeNode(Int.MAX_VALUE)
    private val nullValue = "#"

    // Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        if (root == null) return nullValue
        val queue = ArrayDeque<TreeNode>()
        queue.add(root)
        val nodes = mutableListOf<String>()
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()

            if (node == nullNode) {
                nodes.add(nullValue.toString())
            } else {
                nodes.add(node.`val`.toString())
                if (node.left != null) {
                    queue.addLast(node.left!!)
                } else {
                    queue.addLast(nullNode)
                }

                if (node.right != null) {
                    queue.addLast(node.right!!)
                } else {
                    queue.addLast(nullNode)
                }
            }
        }
        return nodes.joinToString(",")
    }

    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        if (data.isEmpty()) return null
        val splits = data.split(",")
        val root = TreeNode(splits.first().toInt())
        var i = 1
        val queue = ArrayDeque<TreeNode>()
        queue.addLast(root)
        while (queue.isNotEmpty() && i < splits.size) {
            val node = queue.removeFirst()
            if (i < splits.size) {
                if (splits[i] != nullValue) {
                    val left = TreeNode(splits[i].toInt())
                    node.left = left
                    queue.addLast(left)
                }
                i++
            }
            if (i < splits.size) {
                if (splits[i] != nullValue) {
                    val right = TreeNode(splits[i].toInt())
                    node.right = right
                    queue.addLast(right)
                }
                i++
            }
        }
        return root
    }
}