Start learning free

LESSON 421 OF 539 · BINARY TREES

Serialize and Deserialize a Binary Tree in C#: 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 21

Guided

Ctrl + Enter to check

C# · BINARY TREES

Serialize And Deserialize Binary Tree in C#, explained

Problem overview

The class Codec has two methods. Serialize(TreeNode root) turns a binary tree, possibly empty, into a string. Deserialize(string data) takes a string that Serialize produced and rebuilds the same tree, with the same shape and the same value in every node. The format is up to you. The lesson provides the TreeNode class (val, left, right), as the starter code's comment shows.

The tests serialize a tree with one Codec object and rebuild it with the Deserialize of a second one. So everything the rebuild needs must be inside the string; the two objects share nothing else.

For the tree with root 1, left child 2 and right child 3, whose children are 4 and 5, the format used here gives 1,2,#,#,3,4,#,#,5,#,#. Reading it back gives the tree again.

Approach: preorder with a marker for every missing child

A list of values alone is not enough. The values 1,2,3 could be a line going left, a line going right, or a root with two children. What removes the doubt is recording the missing children too.

Write the tree in preorder: a node, then its whole left subtree, then its whole right subtree. For every null child, write the marker #. Now each subtree in the string is self-describing: reading a subtree means reading one piece, and if it is a number, reading a left subtree and then a right subtree right after it; if it is #, the subtree is empty and reading stops. The reader always knows where a subtree ends, so the string alone is enough.

Commas separate the pieces, so values with several digits or a minus sign, like -100, are read back whole.

Step by step

Field values: a List<string> holding the pieces. Both methods work with it, and the helpers need to reach it.
In Serialize, start values as a new empty list, so each call begins from scratch.
Call the helper Write(root), which adds the pieces of the whole tree in preorder.
Return string.Join(",", values), the pieces glued into one line with commas between them.
Write void Write(TreeNode node). It adds the pieces for the subtree under node.
Missing child: if node is null, add "#" to values.
Return early after the marker: an empty child has nothing below it.
Write the node: add node.val.ToString(). The node comes first, which is what preorder means.
Write the left subtree with Write(node.left).
Write the right subtree with Write(node.right).
Field pos: an int, the position of the next piece Deserialize reads.
In Deserialize, cut the string back into pieces with data.Split(','), and put them into a new List<string> stored in values.
Start pos at 0. The first piece is the root, or # for an empty tree.
Return Read(), which reads one whole subtree starting at pos. Called at the start, that is the whole tree.
Write TreeNode Read(). It mirrors Write: pieces are read in the order they were written.
Take the next piece: value = values[pos], then pos++.
Marker: if value is "#", return null.
Otherwise create the node with new TreeNode(int.Parse(value)).
Left subtree: node.left = Read(). This call consumes all the pieces of the left subtree, markers included, and stops exactly where the right subtree begins.
Right subtree: node.right = Read().
Return node.

The solution in C#

class Codec {
    List<string> values;
    int pos;

    void Write(TreeNode node) {
        if (node == null) {
            values.Add("#");
            return;
        }
        values.Add(node.val.ToString());
        Write(node.left);
        Write(node.right);
    }

    public string Serialize(TreeNode root) {
        values = new List<string>();
        Write(root);
        return string.Join(",", values);
    }

    TreeNode Read() {
        string value = values[pos];
        pos++;
        if (value == "#") {
            return null;
        }
        TreeNode node = new TreeNode(int.Parse(value));
        node.left = Read();
        node.right = Read();
        return node;
    }

    public TreeNode Deserialize(string data) {
        values = new List<string>(data.Split(','));
        pos = 0;
        return Read();
    }
}

C# details worth knowing:

Method names are PascalCase. In C# the public methods are Serialize and Deserialize. Code ported from other languages often has lowercase names that C# would not match.
string.Join(",", values) takes a separator and any sequence of strings, such as a List<string>. For the empty tree, values holds just "#", so the result is #.
Split(',') takes a char and returns a string[]. The List<string> constructor accepts that array (any IEnumerable<string>) and copies it into a list.
int.Parse understands a leading minus sign, so "-100" becomes -100. It throws a FormatException on text that isn't a number; here it only sees pieces that Serialize wrote.
Fields without a modifier are private. values, pos, Write and Read are private to Codec, and only Serialize and Deserialize are public.
Deep recursion. Each call of Write or Read handles one node, so the stack is as deep as the tree is tall. The lesson limits depth to 400 levels, which is safe.

Complexity

Time: O(n) for both methods, where n is the number of nodes. Write is called once per node plus once per missing child, which is 2n + 1 calls in all, and each adds one piece. Read consumes each of those pieces exactly once. Joining and splitting the string also take time proportional to its length.

Space: O(n). The list and the string both hold about 2n + 1 pieces, plus the recursion stack, whose depth is the height of the tree.

Edge cases and common mistakes

The empty tree. Serialize(null) returns # and Deserialize("#") returns null. Returning an empty string instead would make Split produce one empty piece, and int.Parse("") would throw.
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 unchanged. Without a separator, -1 and -100 could not be told apart from other digit runs.
Leaving out the # markers. A preorder list of values alone does not identify a tree, because different shapes give the same list.
Not resetting pos. Deserialize sets pos = 0 before reading. Forgetting this would break any second use of the same Codec object.
Using the same values list for both directions without rebuilding it. Each method starts by assigning a fresh list, so a leftover list from an earlier call can't leak in.

Testing

Serializing the tree below with one Codec, rebuilding it with another, and printing it level by level gives:

tree [1,2,3,null,null,4,5]
  string:  1,2,#,#,3,4,#,#,5,#,#
  rebuilt: [1,2,3,null,null,4,5]

tree [-1,0,null,null,-100]
  string:  -1,0,#,-100,#,#,#
  rebuilt: [-1,0,null,null,-100]

empty tree
  string:  #
  rebuilt: []

tree [7]
  string:  7,#,#

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

Start learning free