Serialize and Deserialize Binary Tree

Hard

The problem

Write serialize to turn a binary tree into a string, and deserialize to turn that string back into the same tree. You choose the string format; the only rule is that deserialize(serialize(root)) gives back a tree identical to root.

Example 1
Input: root = [1, 2, 3, null, null, 4, 5] data = serialize(root) deserialize(data)
Output: [1, 2, 3, null, null, 4, 5]
The rebuilt tree has the same shape and values as the original.
Example 2
Input: root = []
Output: []
An empty tree must also survive the round trip.

Limits

0 ≤ number of nodes ≤ 10,000
-1000 ≤ node value ≤ 1000
Values can be negative, so choose separators carefully

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Write nil children explicitly so the structure can be rebuilt unambiguously.

The idea

Preorder DFS to a comma-separated string with "N" for nil; deserialize by reading tokens in the same order recursively.

Target: O(n) time and space

Go function shape

func (c *Codec) serialize(root *TreeNode) string
func (c *Codec) deserialize(data string) *TreeNode

Reference solution

Tested with go test. Try it yourself first, then compare.

// Serialize writes the tree in preorder with "N" for a missing child, so the shape is unambiguous.
func Serialize(root *TreeNode) string {
	var parts []string
	var walk func(*TreeNode)
	walk = func(n *TreeNode) {
		if n == nil {
			parts = append(parts, "N")
			return
		}
		parts = append(parts, strconv.Itoa(n.Val))
		walk(n.Left)
		walk(n.Right)
	}
	walk(root)
	return strings.Join(parts, ",")
}

// Deserialize reads the same tokens in the same order: each call consumes one token, then its two subtrees.
func Deserialize(data string) *TreeNode {
	tokens := strings.Split(data, ",")
	i := 0
	var build func() *TreeNode
	build = func() *TreeNode {
		tok := tokens[i]
		i++
		if tok == "N" {
			return nil
		}
		v, _ := strconv.Atoi(tok)
		return &TreeNode{Val: v, Left: build(), Right: build()}
	}
	return build()
}

Read the lesson: Trees: BFS / DFS