297. Serialize and Deserialize Binary Tree

Problem Link

The goal is to convert a binary tree into a string and then reconstruct the same tree from that string. In practice, we can choose any traversal algorithm, but we use preorder traversal since it allows us to encounter the root first, which simplifies the implementation. Another important point is to explicitly encode null children so that the tree structure is preserved.

Below solution uses an iterative preorder traversal. We traverse the tree using a stack. When a node is visited, we record its value and push its right and left children onto the stack. If a node is None, we record a special marker "N". By doing this consistently, the serialized string uniquely represents both the values and structure of the tree.

During deserialization, we reverse this process. The serialized string is split using a delimiter, and the first value becomes the root. While rebuilding the tree, each node needs to be processed for both its left and right children. Since preorder traversal visits the left subtree before the right subtree, we may encounter the same parent node at different stages.

To handle this, we keep an additional state variable that tracks whether a node's left subtree has already been processed. If the left subtree is complete, we then proceed to build the right subtree. This allows us to reconstruct the tree correctly while following the preorder sequence.

Runtime Complexity

Time: \(O(n)\), where \(n\) is the number of nodes in the tree

Space: \(O(n)\), for the serialized string and stack used during traversal

PythonGo

class Codec:
    DELIMITER = "$"

    def serialize(self, root):
        if not root: return ""
        res = []
        stk = [root]
        while stk:
            node = stk.pop()
            if node:
                val = node.val
                stk.append(node.right)
                stk.append(node.left)
            else:
                val = "N"

            res.append(str(val))

        return self.DELIMITER.join(res)

    def deserialize(self, data):
        if not data: return []
        res = data.split(self.DELIMITER)
        root = TreeNode(res[0])
        stk = [(root, False)] # node, left processed?
        idx = 1
        while stk and idx < len(res):
            node, processed = stk.pop()
            val = res[idx]
            if not processed: # process left first
                if val != "N":
                    node.left = TreeNode(int(val))
                    stk.append((node, True))
                    stk.append((node.left, False))
                else:
                    stk.append((node, True))
                idx+=1
            else: # process right else
                if val != "N":
                    node.right = TreeNode(int(val))
                    stk.append((node.right, False))
                idx+=1
        return root

type Codec struct {
    Delimiter string
}

func ConstructorBT() Codec {
    return Codec{Delimiter: "$"}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return ""
    }
    res := make([]string, 0)
    stk := make([]*TreeNode, 0)
    stk = append(stk, root)
    for len(stk) > 0 {
        node := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        if node != nil {
            res = append(res, strconv.Itoa(node.Val))
            stk = append(stk, node.Right)
            stk = append(stk, node.Left)
        } else {
            res = append(res, "N")
        }
    }
    return strings.Join(res, this.Delimiter)
}

type Pair struct {
    node  *TreeNode
    state bool
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {

    if len(data) == 0 {
        return nil
    }

    res := strings.Split(data, this.Delimiter)
    val, _ := strconv.Atoi(res[0])
    root := &TreeNode{Val: val}
    stk := make([]Pair, 0)
    stk = append(stk, Pair{node: root, state: false})
    i := 1
    for len(stk) > 0 && i < len(res) {
        pair := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        node, processed := pair.node, pair.state
        if !processed {
            if res[i] != "N" {
                val, _ = strconv.Atoi(res[i])
                node.Left = &TreeNode{Val: val}
                stk = append(stk, Pair{node: node, state: true})
                stk = append(stk, Pair{node: node.Left, state: false})
            } else {
                node.Left = nil
                stk = append(stk, Pair{node: node, state: true})
            }
            i++
        } else {
            if res[i] != "N" {
                val, _ = strconv.Atoi(res[i])
                node.Right = &TreeNode{Val: val}
                stk = append(stk, Pair{node: node.Right, state: false})
            } else {
                node.Right = nil
            }
            i++
        }
    }
    return root
}

---