Start learning free

LESSON 422 OF 540 · BINARY TREES

Serialize and Deserialize Binary Tree in Go: Preorder with Markers

Practice O(n) Read the full explanation

Serializing a tree turns it into a string, so it can be saved in a file or sent over a network. Deserializing rebuilds the same tree from that string.

Implement the class Codec:

serialize(root) gets the root of a binary tree, which may be empty, and returns a string.
deserialize(data) gets a string made by serialize and returns the root of the same tree: the same shape, with the same value in every node.

The string's format is up to you. The tests serialize each tree with one Codec, rebuild it with a second Codec's deserialize, and print the rebuilt tree level by level, from left to right, with null where a child is missing and the trailing nulls left out. The trees below are written the same way. serialize must return a string. The starter code spells these names the way your language does.

Example 1:

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

Explanation: One string that works lists the nodes in preorder, with # for a missing child: "1,2,#,#,3,4,#,#,5,#,#". Reading it back gives the same tree.

Example 2:

Input: root = []
Output: []
Explanation: The empty tree needs a string too, for example "#", and deserialize gives back an empty tree.

Example 3:

Input: root = [-1,0,null,null,-100]
Output: [-1,0,null,null,-100]
    -1
    /
   0
    \
   -100

Explanation: Values can be negative and have several digits. With commas between the pieces, as in "-1,0,#,-100,#,#,#", every value is read back whole.

Constraints:

The number of nodes in the tree is in the range [0, 2 * 10⁵].
Each node value is between -1000 and 1000.
The tree is at most 400 levels deep.

Note:

Both serialize and deserialize should run in O(n) time, where n is the number of nodes.

STEP 1 OF 22

Guided

Ctrl + Enter to check

GO · BINARY TREES

Serialize And Deserialize Binary Tree in Go, explained

Problem overview

The lesson asks for a Codec type with two methods:

serialize(root *TreeNode) string turns a binary tree, possibly empty, into a string.
deserialize(data string) *TreeNode takes a string made by serialize and rebuilds the same tree: the same shape and the same value in every node.

The string format is yours to choose. The lesson's tests serialize each tree with one Codec, rebuild it with the deserialize method of a second Codec made by Constructor(), and print the result level by level, with null for missing children. The lesson provides the TreeNode struct, with the fields Val, Left and Right.

For the tree [1,2,3,null,null,4,5], one string that works is 1,2,#,#,3,4,#,#,5,#,#. For the empty tree, the string # is enough, and deserialize gives back an empty tree. Values can be negative or have several digits, such as -100, so the pieces need a separator between them.

Approach: preorder with a marker for every missing child

A list of values alone does not describe a tree: [1,2] could be a node with a left child or with a right child. The fix is to write down the missing children too. The format of this lesson visits the tree in preorder, a node, then its left subtree, then its right subtree, and writes # wherever a child is missing. Pieces are separated by commas.

The markers are what make reading it back unambiguous. When the reader takes a piece, it knows what to do:

A # is a whole empty subtree. Nothing more belongs to it.
A number is a node. The pieces that follow are first its entire left subtree, then its entire right subtree, and each of those is read the same way, recursively.

Because each subtree consumes exactly its own pieces, the reader always knows where the left subtree stops and the right one begins. The reading mirrors the writing, and each piece is visited once, so both methods run in O(n), as the statement requires.

The Codec keeps its working data in struct fields: the slice of pieces and the position of the next piece to read. The helpers write and read are methods that use those fields, so they do not need extra parameters.

Step by step

Declare the first field. values is a []string: the list of pieces, used by both directions.
Write Constructor. Return an empty Codec{}. Every field starts at its zero value, an empty slice and 0, so nothing else needs setting.
Start serialize clean. Set this.values to an empty []string{}, so each call builds its list from scratch.
Call the helper this.write(root). It appends the pieces of the whole tree to this.values in preorder.
Glue the pieces. Return strings.Join(this.values, ","), which joins the slice with a comma between each two pieces.
Declare write as a method: func (this *Codec) write(node *TreeNode). It writes the subtree under node.
Write the marker for a missing child. If node is nil, append "#" to this.values. append returns the longer slice, so the result is assigned back to this.values.
Return right after the marker. An empty child has nothing under it.
Write the node's value. Append strconv.Itoa(node.Val), which converts the int to a string. The node comes first: that is preorder.
Write the left subtree with this.write(node.Left).
Write the right subtree with this.write(node.Right).
Add the second field. pos is an int: the index of the next piece for deserialize to read.
Cut the string back into pieces. In deserialize, strings.Split(data, ",") returns a slice of the strings between the commas. Store it in this.values.
Reset the position with this.pos = 0. The first piece is the root, or # for an empty tree.
Return what this.read() gives. One call reads one whole subtree, which here is the whole tree.
Declare read as func (this *Codec) read() *TreeNode. It reads the subtree that starts at this.pos.
Take the next piece into value and move this.pos forward by one.
Stop on #. If value is "#", return nil.
Convert a number. strconv.Atoi(value) returns the number and an error. The pieces were produced by serialize, so the error is ignored with _. Then create the node with that value as Val.
Read the left subtree with node.Left = this.read(). The call consumes all the pieces of the left subtree, markers included.
Read the right subtree the same way into node.Right.
Return the node.

The solution in Go

type Codec struct {
	values []string
	pos    int
}

func Constructor() Codec {
	return Codec{}
}

func (this *Codec) serialize(root *TreeNode) string {
	this.values = []string{}
	this.write(root)
	return strings.Join(this.values, ",")
}

func (this *Codec) write(node *TreeNode) {
	if node == nil {
		this.values = append(this.values, "#")
		return
	}
	this.values = append(this.values, strconv.Itoa(node.Val))
	this.write(node.Left)
	this.write(node.Right)
}

func (this *Codec) deserialize(data string) *TreeNode {
	this.values = strings.Split(data, ",")
	this.pos = 0
	return this.read()
}

func (this *Codec) read() *TreeNode {
	value := this.values[this.pos]
	this.pos++
	if value == "#" {
		return nil
	}
	number, _ := strconv.Atoi(value)
	node := &TreeNode{Val: number}
	node.Left = this.read()
	node.Right = this.read()
	return node
}

The Go details worth knowing:

Methods on a struct. Go has no classes. Codec is a struct, and func (this *Codec) write(...) attaches a method to it. The receiver is a pointer, *Codec, so the method changes the caller's fields. With a value receiver, the changes to values and pos would be lost when the method returns. The name this is only a convention; any name works.
append and reassignment. append may allocate a new, bigger array, so it returns the slice to use from then on. Writing just append(this.values, "#") and discarding the result would be a compile error, because the result of append must be used.
Zero values. Codec{} gives values as a nil slice and pos as 0. A nil slice works with append, and serialize replaces it anyway.
strconv.Itoa and strconv.Atoi. Itoa turns an int into its decimal text, with the minus sign for negatives. Atoi goes the other way and returns (int, error). Converting with string(node.Val) instead would produce the character with that code point, not the digits.
Why a separator. Without commas, the pieces 1, 12 and -3 could not be told apart when read back as one string. strings.Split on the comma recovers them exactly.
Shared state. values and pos are reused by every call. Both methods reset what they need at the start, so one Codec can serialize several trees in a row.

Complexity

Time: O(n) for both methods, where n is the number of nodes. write is called once per node and once per missing child, which is at most 2n + 1 calls in total. strings.Join and strings.Split each pass over the string once. read consumes one piece per call, so it runs the same number of times.

Space: O(n). The slice of pieces holds 2n + 1 strings, and the output string has a similar size. The recursion adds a stack as deep as the tree is tall, up to 400 levels in this lesson. Go grows its stacks as needed, so even a tree that is a chain of 200,000 nodes works.

Edge cases and common mistakes

The empty tree. serialize(nil) returns "#". deserialize("#") reads that one piece and returns nil. Skipping the marker for nil would make the empty tree produce an empty string, which strings.Split turns into one empty piece, not a #, and Atoi would fail on it.
A single node. A tree with only the value 7 becomes 7,#,#.
Negative and multi-digit values. The tree [-1,0,null,null,-100] becomes -1,0,#,-100,#,#,# and comes back whole, because every number is a separate piece.
Left-only versus right-only trees. The tree [1,2] becomes 1,2,#,#,#, while a tree with only a right child 2 becomes 1,#,2,#,#. The markers keep these apart.
Forgetting to advance pos. Every call of read must move forward by one, or the recursion reads the same piece forever.
Using # as a value. The marker is safe here because node values are numbers, and a number's text never equals #.
Using a value receiver. A method declared on Codec instead of *Codec would work on a copy, so pos would never advance for the caller.

Testing

Each tree below is serialized, then rebuilt with a second Codec.

[1,2,3,null,null,4,5] becomes 1,2,#,#,3,4,#,#,5,#,# and is rebuilt as [1,2,3,null,null,4,5].
The empty tree becomes # and is rebuilt as [].
[-1,0,null,null,-100] becomes -1,0,#,-100,#,#,# and is rebuilt as [-1,0,null,null,-100].
[7] becomes 7,#,# and is rebuilt as [7].
[1,2,3] becomes 1,2,#,#,3,#,# and is rebuilt as [1,2,3].
[1000,-1000] becomes 1000,-1000,#,#,# and is rebuilt as [1000,-1000].

Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free