Skip to main content

🟥 Serialize and Deserialize Binary Tree (#297)

🔗 Problem Link​

📋 Problem Statement​

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

💡 Examples​

Example 1​

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2​

Input: root = []
Output: []

🔑 Key Insights & Approach​

Core Observation: Use preorder traversal with null markers. Preorder allows reconstruction without ambiguity.

Why Preorder with Null Markers?

  • O(n) time for both operations
  • O(n) space
  • Unambiguous reconstruction
  • Handles any tree structure

Approaches:

  1. Preorder with null markers: O(n) - optimal
  2. Level-order with null markers: O(n)

Pattern: "Tree Serialization" using traversal with markers.

🐍 Solution: Python​

Approach: Preorder with Null Markers​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string."""
        result = []

        def dfs(node):
            if not node:
                result.append("null")
                return

            result.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(result)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree."""
        values = data.split(",")
        self.index = 0

        def dfs():
            if values[self.index] == "null":
                self.index += 1
                return None

            node = TreeNode(int(values[self.index]))
            self.index += 1

            node.left = dfs()
            node.right = dfs()

            return node

        return dfs()

Approach 2: Using Iterator​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import Optional

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        result = []

        def preorder(node):
            if not node:
                result.append("#")
            else:
                result.append(str(node.val))
                preorder(node.left)
                preorder(node.right)

        preorder(root)
        return " ".join(result)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        def build(values):
            val = next(values)
            if val == "#":
                return None

            node = TreeNode(int(val))
            node.left = build(values)
            node.right = build(values)
            return node

        return build(iter(data.split()))

🔵 Solution: Golang​

Approach: Preorder​

Time Complexity: O(n) | Space Complexity: O(n)

import (
    "strconv"
    "strings"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type Codec struct {
    index int
}

func Constructor() Codec {
    return Codec{}
}

func (codec *Codec) serialize(root *TreeNode) string {
    result := []string{}

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            result = append(result, "null")
            return
        }

        result = append(result, strconv.Itoa(node.Val))
        dfs(node.Left)
        dfs(node.Right)
    }

    dfs(root)
    return strings.Join(result, ",")
}

func (codec *Codec) deserialize(data string) *TreeNode {
    values := strings.Split(data, ",")
    codec.index = 0

    var dfs func() *TreeNode
    dfs = func() *TreeNode {
        if values[codec.index] == "null" {
            codec.index++
            return nil
        }

        val, _ := strconv.Atoi(values[codec.index])
        node := &TreeNode{Val: val}
        codec.index++

        node.Left = dfs()
        node.Right = dfs()

        return node
    }

    return dfs()
}

📚 References​