LeetCode 449 - Serialize and Deserialize BST

LeetCode Problem 449

Difficulty: 🟡 Medium
Topics: String, Tree, Depth-First Search, Breadth-First Search, Design, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem asks us to design two operations for a Binary Search Tree, abbreviated as BST:

• serialize(root) converts the BST into a string representation.
• deserialize(data) reconstructs the exact same BST from that string.

The important requirement is that the deserialized tree must match the original tree structure and node values. The format itself is completely up to us, which means we can choose any encoding strategy as long as it is reversible.

A Binary Search Tree has a critical property:

• Every node in the left subtree has a value smaller than the current node.
• Every node in the right subtree has a value larger than the current node.

This property is the key observation that allows us to create a compact serialization format.

The input is the root node of a BST. The output of serialization is a string. The output of deserialization is the reconstructed root node.

The constraints tell us several important things:

• The tree can contain up to 10^4 nodes, so the algorithm must be efficient.
• Node values are between 0 and 10^4.
• The tree is guaranteed to be a valid BST, which allows us to take advantage of BST ordering rules during reconstruction.

A naive serialization format might include explicit null markers for missing children. While that works for any binary tree, it wastes space because BST structure can already be inferred from traversal order.

Important edge cases include:

• An empty tree, where serialization should produce an empty string and deserialization should return None.
• A tree with only one node.
• A completely skewed BST, where all nodes go only left or only right. This creates recursion depth concerns and worst-case recursion stack usage.
• Trees with many levels where reconstruction logic must correctly maintain BST boundaries.

Approaches

Brute Force Approach

A straightforward solution is to treat the BST like a normal binary tree and serialize it using level-order traversal or preorder traversal with explicit null markers.

For example, a preorder serialization might look like:

2,1,null,null,3,null,null

During deserialization, we recursively rebuild the tree by reading values one by one. Whenever we encounter null, we return an empty child.

This approach works correctly because every node and every missing child is explicitly encoded, making reconstruction unambiguous.

However, this solution is not space efficient. A BST already contains ordering information that can help reconstruct structure without storing null placeholders. Including null markers increases serialized size significantly, especially for sparse trees.

Optimal Approach

The key insight is that a BST can be uniquely reconstructed from its preorder traversal alone.

In preorder traversal:

1. Visit root
2. Traverse left subtree
3. Traverse right subtree

Because BST nodes follow ordering constraints, we can determine where the left subtree ends and the right subtree begins without storing null markers.

For example:

      8
     / \
    5   10
   / \    \
  1   7    12

Preorder traversal becomes:

8,5,1,7,10,12

During deserialization:

• The first value is always the root.
• Any following values smaller than the root belong to the left subtree.
• Any following values larger than the root belong to the right subtree.
• Recursive value bounds allow us to rebuild the tree efficiently.

This produces a compact serialization while maintaining linear time complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Stores null markers explicitly, wastes space
Optimal	O(n)	O(n)	Uses BST preorder properties for compact encoding

Algorithm Walkthrough

Serialization

1. Perform a preorder traversal of the BST.

Preorder traversal visits nodes in the order:

• root
• left subtree
• right subtree

This traversal is important because the first element always identifies the subtree root. 2. Append each node value into a list of strings.

We avoid null markers entirely because BST ordering rules are sufficient for reconstruction. 3. Join all values using commas.

The final serialized string is compact because it stores only actual node values.

Deserialization

1. Split the serialized string by commas.

This reconstructs the preorder traversal sequence. 2. Maintain a shared index pointer.

The pointer tracks which value we are currently processing. 3. Use recursive bounds during reconstruction.

Every recursive call receives:

• a lower bound
• an upper bound

These bounds define the valid range for nodes in the current subtree. 4. Read the current preorder value.

If the value falls outside the allowed range, it does not belong to the current subtree, so return None. 5. Create the current node.

Increment the preorder index because this value has now been consumed. 6. Recursively build the left subtree.

The left subtree must contain values:

lower < value < current node value

7. Recursively build the right subtree.

The right subtree must contain values:

current node value < value < upper

8. Return the constructed node.

Why it works

The preorder traversal guarantees that each subtree root appears before all nodes in that subtree. The BST ordering property guarantees that every node belongs within a unique numeric range. Combining preorder order with recursive bounds ensures that every node is reconstructed in exactly the correct position.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from typing import Optional
import math

class Codec:

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

        def preorder(node: Optional[TreeNode]) -> None:
            if not node:
                return

            preorder_values.append(str(node.val))
            preorder(node.left)
            preorder(node.right)

        preorder(root)

        return ",".join(preorder_values)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree."""
        
        if not data:
            return None

        preorder_values = list(map(int, data.split(",")))
        index = 0

        def build(lower: int, upper: int) -> Optional[TreeNode]:
            nonlocal index

            if index >= len(preorder_values):
                return None

            value = preorder_values[index]

            if value < lower or value > upper:
                return None

            index += 1

            node = TreeNode(value)

            node.left = build(lower, value)
            node.right = build(value, upper)

            return node

        return build(-math.inf, math.inf)

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans

The serialization method performs a preorder DFS traversal and records node values in traversal order. Because preorder always visits the root first, it naturally supports recursive reconstruction later.

The deserialization method converts the string back into integers and reconstructs the BST using recursive bounds. The index variable tracks the current preorder element being processed. Each recursive call validates whether the current value belongs inside the allowed BST range.

The lower and upper bounds enforce BST correctness automatically. If a value falls outside the valid range, it belongs to a different subtree, so recursion stops.

This approach avoids null markers entirely, making the serialized representation compact.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import (
	"math"
	"strconv"
	"strings"
)

type Codec struct {
	
}

func Constructor() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	values := []string{}

	var preorder func(node *TreeNode)

	preorder = func(node *TreeNode) {
		if node == nil {
			return
		}

		values = append(values, strconv.Itoa(node.Val))

		preorder(node.Left)
		preorder(node.Right)
	}

	preorder(root)

	return strings.Join(values, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "" {
		return nil
	}

	parts := strings.Split(data, ",")
	preorderValues := make([]int, len(parts))

	for i, part := range parts {
		value, _ := strconv.Atoi(part)
		preorderValues[i] = value
	}

	index := 0

	var build func(lower int, upper int) *TreeNode

	build = func(lower int, upper int) *TreeNode {
		if index >= len(preorderValues) {
			return nil
		}

		value := preorderValues[index]

		if value < lower || value > upper {
			return nil
		}

		index++

		node := &TreeNode{Val: value}

		node.Left = build(lower, value)
		node.Right = build(value, upper)

		return node
	}

	return build(math.MinInt, math.MaxInt)
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor()
 * deser := Constructor()
 * tree := ser.serialize(root)
 * ans := deser.deserialize(tree)
 * return ans
 */

The Go implementation follows the same algorithmic structure as the Python version. The main differences are language specific.

Go uses slices instead of Python lists and requires explicit string-to-integer conversion using strconv.Atoi. Nil pointers are represented with nil rather than None.

The recursive helper function captures the shared index variable through closure semantics, similar to Python's nonlocal.

Worked Examples

Example 1

Input:

root = [2,1,3]

BST structure:

    2
   / \
  1   3

Serialization Walkthrough

Step	Current Node	Serialized Values
1	2	["2"]
2	1	["2", "1"]
3	null	["2", "1"]
4	null	["2", "1"]
5	3	["2", "1", "3"]

Final serialized string:

"2,1,3"

Deserialization Walkthrough

Preorder values:

[2,1,3]

Step	Index	Value	Bounds	Action
1	0	2	(-inf, inf)	Create root
2	1	1	(-inf, 2)	Create left child
3	2	3	(-inf, 1)	Invalid, return None
4	2	3	(1, 2)	Invalid, return None
5	2	3	(2, inf)	Create right child

Final tree:

    2
   / \
  1   3

Example 2

Input:

root = []

Serialization

The root is None, so preorder traversal visits nothing.

Serialized result:

""

Deserialization

The input string is empty.

Return:

None

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once during serialization and deserialization
Space	O(n)	Preorder array and recursion stack together require linear space

The serialization traversal touches each node one time, producing linear complexity. During deserialization, every preorder value is consumed exactly once, so reconstruction is also linear.

The recursion stack depends on tree height. In the worst case of a skewed BST, recursion depth becomes O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

codec = Codec()

# Test 1: Empty tree
root = None
serialized = codec.serialize(root)
deserialized = codec.deserialize(serialized)
assert deserialized is None  # empty tree case

# Test 2: Single node
root = TreeNode(5)
serialized = codec.serialize(root)
deserialized = codec.deserialize(serialized)
assert inorder(deserialized) == [5]  # single node reconstruction

# Test 3: Balanced BST
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

serialized = codec.serialize(root)
deserialized = codec.deserialize(serialized)
assert inorder(deserialized) == [1, 2, 3]  # balanced BST

# Test 4: Left skewed BST
root = TreeNode(5)
root.left = TreeNode(4)
root.left.left = TreeNode(3)
root.left.left.left = TreeNode(2)

serialized = codec.serialize(root)
deserialized = codec.deserialize(serialized)
assert inorder(deserialized) == [2, 3, 4, 5]  # left skewed tree

# Test 5: Right skewed BST
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
root.right.right.right = TreeNode(4)

serialized = codec.serialize(root)
deserialized = codec.deserialize(serialized)
assert inorder(deserialized) == [1, 2, 3, 4]  # right skewed tree

# Test 6: Larger BST
root = TreeNode(8)
root.left = TreeNode(5)
root.right = TreeNode(10)
root.left.left = TreeNode(1)
root.left.right = TreeNode(7)
root.right.right = TreeNode(12)

serialized = codec.serialize(root)
deserialized = codec.deserialize(serialized)
assert inorder(deserialized) == [1, 5, 7, 8, 10, 12]  # complex BST

# Test 7: Zero value node
root = TreeNode(0)

serialized = codec.serialize(root)
deserialized = codec.deserialize(serialized)
assert inorder(deserialized) == [0]  # minimum value constraint

print("All tests passed!")

Test	Why
Empty tree	Validates handling of null input
Single node	Ensures simplest non-empty BST works
Balanced BST	Tests standard reconstruction
Left skewed BST	Tests worst-case left recursion
Right skewed BST	Tests worst-case right recursion
Larger BST	Verifies complex subtree reconstruction
Zero value node	Confirms lower bound values work correctly

Edge Cases

Empty Tree

An empty BST is one of the most common sources of bugs because serialization may accidentally produce invalid separators or deserialization may attempt to parse empty input.

This implementation handles the case explicitly. Serialization returns an empty string, and deserialization immediately returns None when given empty data.

Completely Skewed Tree

A BST can become entirely left skewed or right skewed, behaving like a linked list. This creates worst-case recursion depth.

For example:

5
 \
  6
   \
    7

The implementation still works correctly because preorder traversal naturally preserves insertion order and the recursive bounds correctly restrict subtree placement.

The complexity remains linear, although recursion stack depth becomes O(n).

Boundary Values

The problem allows node values from 0 to 10^4. Boundary handling is important because incorrect comparisons may accidentally reject valid nodes.

The implementation uses negative and positive infinity in Python and math.MinInt and math.MaxInt in Go to ensure all valid node values fit safely within initial bounds.

This guarantees that even the smallest and largest allowed node values deserialize correctly.