-
Notifications
You must be signed in to change notification settings - Fork 0
090 — Serialize and Deserialize Binary Tree
LeetCode 297 · Hard. Design an algorithm to serialize a binary tree to a single string, and deserialize that string back to the original tree structure — the tree can contain any values, including duplicates, and may be shaped any way at all.
To rebuild a tree from a flat string, the string has to encode not just values but shape — where every branch ends, and where every gap (missing child) is. One instinct is to reserve a fixed array slot for every position a node could ever occupy in a complete binary tree — root at index 0, its children at 1 and 2, their children at 3, 4, 5, 6, and so on — and just leave slots empty wherever a real node doesn't exist. That works, but it reserves space for the tree's worst-case shape, not its actual one: a tree that happens to zigzag down one side for n nodes would need an array sized for a complete tree of the same height, which is exponentially bigger than n. A better encoding writes down only what actually exists — every real value, plus an explicit marker every time a child is missing — so the string's size tracks the tree's actual node count, no matter how it's shaped.
"Serialize a tree to a string and reconstruct it exactly" is the cue to do a preorder DFS (root, then left, then right) while writing an explicit null marker (like "#") every time a recursive call hits a missing child. Because preorder always visits parents before children, deserializing can consume the same token stream in the same order it was written, rebuilding the tree top-down without needing to search for anything.
Encode the tree the way a complete binary tree would sit in an array — root at index 0, and for any node at index i, its left child at 2i + 1 and its right child at 2i + 2 — leaving nil in slots where no node exists.
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val }
}
class CodecBruteForce {
func serialize(_ root: TreeNode?) -> [Int?] {
var array: [Int?] = []
fill(root, 0, &array)
return array
}
private func fill(_ node: TreeNode?, _ index: Int, _ array: inout [Int?]) {
guard let node = node else { return }
while array.count <= index {
array.append(nil)
}
array[index] = node.val
fill(node.left, 2 * index + 1, &array)
fill(node.right, 2 * index + 2, &array)
}
func deserialize(_ array: [Int?]) -> TreeNode? {
return build(array, 0)
}
private func build(_ array: [Int?], _ index: Int) -> TreeNode? {
guard index < array.count, let val = array[index] else { return nil }
let node = TreeNode(val)
node.left = build(array, 2 * index + 1)
node.right = build(array, 2 * index + 2)
return node
}
}
// smoke test: a right-only skewed chain of 4 nodes — 1 -> 2 -> 3 -> 4, all via right children
let bfSkewed = TreeNode(1)
bfSkewed.right = TreeNode(2)
bfSkewed.right?.right = TreeNode(3)
bfSkewed.right?.right?.right = TreeNode(4)
let bfCodec = CodecBruteForce()
let bfArray = bfCodec.serialize(bfSkewed)
print(bfArray.count) // 15 — indices 0,2,6,14 hold values; everything else is nil filler up to index 14
let bfRebuilt = bfCodec.deserialize(bfArray)
print(bfRebuilt?.val ?? -1, bfRebuilt?.right?.val ?? -1, bfRebuilt?.right?.right?.val ?? -1, bfRebuilt?.right?.right?.right?.val ?? -1) // 1 2 3 4Big-O: O(n) time to serialize/deserialize the given tree, but O(2^h) space in the worst case — a right-only (or left-only) chain of n nodes has height h = n - 1 (in edges), and its deepest node lands at array index 2^(h+1) - 2, so the array balloons to 2^(h+1) - 1 total slots for only n real values (confirmed by the smoke test below: a 4-node chain of height 3 produces an array of size 2^4 - 1 = 15). This is exponential blowup relative to the actual node count on a skewed tree.
Do a preorder DFS, writing every node's value as a token — and writing an explicit "#" token every time a child is missing — joined into one string. To deserialize, split the string back into tokens and consume them in the same order, rebuilding root, then left subtree, then right subtree.
class Codec {
func serialize(_ root: TreeNode?) -> String {
var tokens: [String] = []
func dfs(_ node: TreeNode?) {
guard let node = node else {
tokens.append("#")
return
}
tokens.append(String(node.val))
dfs(node.left)
dfs(node.right)
}
dfs(root)
return tokens.joined(separator: ",")
}
func deserialize(_ data: String) -> TreeNode? {
var tokens = data.split(separator: ",").map(String.init)[...]
func build() -> TreeNode? {
guard let token = tokens.first else { return nil }
tokens = tokens.dropFirst()
if token == "#" {
return nil
}
let node = TreeNode(Int(token)!)
node.left = build()
node.right = build()
return node
}
return build()
}
}
// smoke test: same skewed chain as above — 1 -> 2 -> 3 -> 4, all via right children
let skewed = TreeNode(1)
skewed.right = TreeNode(2)
skewed.right?.right = TreeNode(3)
skewed.right?.right?.right = TreeNode(4)
let codec = Codec()
let encoded = codec.serialize(skewed)
print(encoded) // "1,#,2,#,3,#,4,#,#"
let rebuilt = codec.deserialize(encoded)
print(rebuilt?.val ?? -1, rebuilt?.right?.val ?? -1, rebuilt?.right?.right?.val ?? -1, rebuilt?.right?.right?.right?.val ?? -1) // 1 2 3 4
// empty tree round-trip
print(codec.serialize(nil)) // "#"
print(codec.deserialize("#") == nil) // true
// single node round-trip
print(codec.deserialize(codec.serialize(TreeNode(42)))?.val ?? -1) // 42Big-O: O(n) time and O(n) space for both directions, regardless of the tree's shape — exactly one token is written per real node and one "#" per missing child, so the string's length scales linearly with the actual node count, never with 2^h.
The array-index encoding is shape-agnostic in code — 2i + 1 and 2i + 2 work for any binary tree — but not shape-agnostic in space: it reserves a slot for every position a node could occupy in a complete tree of that height, whether or not a real node lives there, and a skewed tree's height is O(n), which makes 2^h explode relative to n. Marker-based preorder encoding only ever writes down what actually exists — a token per real node, a token per genuine gap — so its size tracks the tree's actual node count, O(n), no matter how lopsided the tree is. The "#" marker is what makes this possible: it lets the deserializer know exactly when a branch ends without ever needing to infer it from array positions.
- Binary Trees — the structure being encoded and rebuilt.
- DFS and Backtracking — preorder traversal (root, then left, then right) is what both serialize and deserialize walk in lockstep.
-
Big-O Notation — for the
O(n)vs.O(2^h)space contrast above.
Serialize and Deserialize Binary Tree is writing down only what's really there — a token per real node, a "#" per real gap — instead of reserving array slots for every position a node could have occupied, which is what keeps the encoding linear no matter how lopsided the tree is.
For the skewed chain 1 -> 2 -> 3 -> 4 (each linked via right, height h = 3), compute the exact size of the brute force's array encoding (using 2i + 1 / 2i + 2) versus the exact number of tokens in the optimal marker-based string. Then explain, in terms of h versus n, why the gap between these two sizes only gets worse as the chain gets longer.
⬅️ Previous: Binary Tree Maximum Path Sum · Next: Implement Trie (Prefix Tree) ➡️