297. Serialize and Deserialize Binary Tree

At a Glance

Topic: trees
Pattern: Tree DFS / String encoding
Difficulty: Hard
Companies: Amazon, Google, Meta, Microsoft, LinkedIn
Frequency: High
LeetCode: 297

Problem (one-liner)

Design serialize and deserialize for a binary tree so that any tree can be encoded to a string and exactly reconstructed. Node values are integers; the tree can be unbalanced and skewed.

Recognition Cues

“Codec / serialize tree”
Preorder (or level-order) with explicit nil markers avoids ambiguity
DFS with delimiter beats naive parentheses-only for odd shapes

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute / naive — explicit tree ADT JSON with full pointer addresses — non-portable / wrong for interviews.
Acceptable — level-order (BFS) with queue; length-prefixed children counts — also O(n) string size; useful if interviewer bans recursion depth.
Optimal (most interviews) — preorder DFS with explicit nil markers between commas — O(n) time, O(n) tokens; deserialize consumes stream recursively or iteratively with stack depth = height.

Optimal Solution

Go

import (
	"strconv"
	"strings"
)

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

func serialize(root *TreeNode) string {
	parts := make([]string, 0)
	var preorder func(node *TreeNode)
	preorder = func(node *TreeNode) {
		if node == nil {
			parts = append(parts, "#")
			return
		}
		parts = append(parts, strconv.Itoa(node.Val))
		preorder(node.Left)
		preorder(node.Right)
	}
	preorder(root)
	return strings.Join(parts, ",")
}

func deserialize(data string) *TreeNode {
	if data == "" {
		return nil
	}
	tokens := strings.Split(data, ",")
	index := 0
	var build func() *TreeNode
	build = func() *TreeNode {
		if index >= len(tokens) {
			return nil
		}
		token := tokens[index]
		index++
		if token == "#" {
			return nil
		}
		value, _ := strconv.Atoi(token)
		return &TreeNode{
			Val:   value,
			Left:  build(),
			Right: build(),
		}
	}
	return build()
}

JavaScript

function serialize(root) {
	const parts = [];
	function preorder(node) {
		if (node === null) {
			parts.push("#");
			return;
		}
		parts.push(String(node.val));
		preorder(node.left);
		preorder(node.right);
	}
	preorder(root);
	return parts.join(",");
}

function deserialize(data) {
	if (data === "") {
		return null;
	}
	const tokens = data.split(",");
	let index = 0;
	function build() {
		if (index >= tokens.length) {
			return null;
		}
		const token = tokens[index];
		index++;
		if (token === "#") {
			return null;
		}
		return {
			val: Number.parseInt(token, 10),
			left: build(),
			right: build(),
		};
	}
	return build();
}

Walkthrough

Tree 1(2,3(4,5)) → preorder string 1,2,#,#,3,4,#,#,5,#,# (commas as separator).

Invariant: preorder with nil tokens uniquely defines one binary tree (reconstruct by consuming linearly).

Edge Cases

Empty tree — string of only # or empty (define contract)
Single node
Left-skewed / right-skewed — string length O(n)
Negative values — strconv / parseInt handle sign in token

Pitfalls

Forgetting trailing nils — childless node still needs Left and Right sentinels
Using Join without consistent delimiter (values can be multi-digit)
TrimSuffix in Go if you always append , at end

Variants

Compact BST encoding (no nulls) — use BST order property; different format.
Streamed bits — varint per node + structure bits to save space.
N-ary tree — Number of children + child list in encoding.

Mind-Map Tags

#tree #serialize #preorder #sentinel #codec #dfs #reconstruct