Serialize and Deserialize Binary Tree in DSA Go - Time & Space Complexity

Time Complexity: Serialize and Deserialize Binary Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to convert a binary tree into a string and back.

How does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Serialize converts a binary tree to a string
func serialize(root *TreeNode) string {
    if root == nil {
        return "#"
    }
    return fmt.Sprintf("%d,%s,%s", root.Val, serialize(root.Left), serialize(root.Right))
}

// Deserialize converts a string back to a binary tree
func deserialize(data string) *TreeNode {
    vals := strings.Split(data, ",")
    var index int
    var build func() *TreeNode
    build = func() *TreeNode {
        if vals[index] == "#" {
            index++
            return nil
        }
        val, _ := strconv.Atoi(vals[index])
        index++
        node := &TreeNode{Val: val}
        node.Left = build()
        node.Right = build()
        return node
    }
    return build()
}
    

This code turns a binary tree into a string and then rebuilds the tree from that string.

Identify Repeating Operations

• Primary operation: Visiting each node once during serialization and deserialization.
• How many times: Exactly once per node in the tree.

How Execution Grows With Input

Each node is processed once, so the work grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The time grows in a straight line as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to serialize or deserialize grows directly with the number of nodes.

Common Mistake

[X] Wrong: "Serialization takes constant time because it just creates a string."

[OK] Correct: The string must include every node, so the process must visit all nodes, which takes time proportional to the tree size.

Interview Connect

Understanding this helps you explain how tree data can be saved and restored efficiently, a common real-world need.

Self-Check

"What if we used a different traversal order (like inorder) for serialization? How would the time complexity change?"