Serialize And Deserialize Binary Tree

The problem

Write two functions. serialize takes root, the top node of a binary tree, and returns one string in a format you choose. deserialize takes that string and returns a tree equal to the original: the same values in the same places. Each node has a whole number val, which may be negative and may appear more than once, and two children, left and right; a missing child is null. The tree may be empty, and then root is null. deserialize runs on a fresh copy of your code and gets only the string: it cannot use anything serialize remembered.

What to write

Implement the named encoder and decoder functions. The judge calls them separately and verifies the round trip.

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":{"val":4,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}}

Output
{"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":{"val":4,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}}

Input
root = null

Output
null

Constraints

Nodes use {val, left, right}; the tree may be empty.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   deserialize gets nothing but the string, so the string has to describe the shape of the tree and not only its values. Values can be negative and can repeat, so think about which characters are safe to put between them.

2. Hint 2: Ask a smaller question

   Write down only the values of two small trees: a 1 whose left child is 2, and a 1 whose right child is 2. Both give 1, 2. What would you have to add so that someone reading the text can tell them apart?

3. Hint 3: Name the pattern

   Write each node before its children: its value, then its whole left subtree, then its whole right subtree, with a marker wherever a child is missing. Reading the text back in the same order rebuilds the tree. Handling a node before its children is preorder tree recursion. Read the lesson on preorder tree recursion.

4. Hint 4: State the invariant

   Call each value or marker in the text a token. deserialize always stands at the first token of a subtree. A marker means that subtree is empty. A value means a node, and right after it come its whole left subtree and then its whole right subtree.

5. Hint 5: Sketch the pseudocode

   serialize(node): for no node return "#". Otherwise return the value, a comma, serialize(left child), a comma, serialize(right child). deserialize: split the text at the commas and keep one shared position. read(): take the next token. For "#" return no node. Otherwise make a node with that number, read() its left child, then read() its right child. Return the first read().

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Write preorder values with explicit null markers. Consume the tokens in the same recursive order to reconstruct the tree.

The slow way

Write only the values in preorder, which means each node before its children, such as 1,2 for a root 1 with one child 2. That text has lost the shape of the tree: it is the same whether 2 is the left child or the right child, so deserialize cannot know which tree to rebuild.

The insight

The shape is lost because a missing child leaves no trace in the text. So write a marker for every missing child too. Then every value is followed by exactly two things, its left subtree and its right subtree. Each of them is either one marker or another value with its own two subtrees, so deserialize always knows what the next piece of text stands for.

Step by step

1. Write "#" for an empty spot. A missing child has to leave a trace in the text, or deserialize cannot tell a left child from a right one. The same marker also stands for a whole empty tree.
2. Write the value, then the left subtree, then the right subtree. With the node first, deserialize meets a value before anything that hangs below it. It can make the node at once and then fill in its two sides. The commas keep the pieces apart.
3. Split the text at the commas and read the tokens from the front. The pieces between the commas are called tokens. A comma never appears inside a number or a marker, so splitting gives back exactly what was written, in the same order.
4. Each call reads one whole subtree, starting at the next token. All the calls share one position in the list of tokens. A token that has been read is used up, so each call starts exactly where the one before it stopped.
5. A "#" token means the spot is empty. The marker stands for a missing child. It uses up one token and gives back no node.
6. Any other token is a value: read its left subtree, then its right. serialize wrote the whole left subtree straight after the value and the right subtree after that. Reading in the same order puts every node back on its own side.
7. The first call reads the whole tree. The whole tree is the subtree that starts at the first token, and reading it uses up every token, so this one call gives back the complete tree.

The same numbered steps are the comments in each solution.

function serialize(root) {
  // 1. Write "#" for an empty spot
  if (!root) return "#";
  // 2. Write the value, then the left subtree, then the right subtree
  return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
function deserialize(data) {
  // 3. Split the text at the commas and read the tokens from the front
  const tokens = data.split(",");
  let i = 0;
  // 4. Each call reads one whole subtree, starting at the next token
  function read() {
    const token = tokens[i++];
    // 5. A "#" token means the spot is empty
    if (token === "#") return null;
    // 6. Any other token is a value: read its left subtree, then its right
    return { val: Number(token), left: read(), right: read() };
  }
  // 7. The first call reads the whole tree
  return read();
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function serialize(root: TreeNode | null): string {
  // 1. Write "#" for an empty spot
  if (!root) return "#";
  // 2. Write the value, then the left subtree, then the right subtree
  return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
function deserialize(data: string): TreeNode | null {
  // 3. Split the text at the commas and read the tokens from the front
  const tokens = data.split(",");
  let i = 0;
  // 4. Each call reads one whole subtree, starting at the next token
  function read(): TreeNode | null {
    const token = tokens[i++];
    // 5. A "#" token means the spot is empty
    if (token === "#") return null;
    // 6. Any other token is a value: read its left subtree, then its right
    return { val: Number(token), left: read(), right: read() };
  }
  // 7. The first call reads the whole tree
  return read();
}

def serialize(root):
    # 1. Write "#" for an empty spot
    if root is None:
        return "#"
    # 2. Write the value, then the left subtree, then the right subtree
    return f"{root.val},{serialize(root.left)},{serialize(root.right)}"


def deserialize(data):
    # 3. Split the text at the commas and read the tokens from the front
    tokens = iter(data.split(","))

    # 4. Each call reads one whole subtree, starting at the next token
    def read():
        token = next(tokens)
        # 5. A "#" token means the spot is empty
        if token == "#":
            return None
        # 6. Any other token is a value: read its left subtree, then its right
        return TreeNode(int(token), read(), read())

    # 7. The first call reads the whole tree
    return read()

Example 1, traced

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":{"val":4,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}}

Output
{"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":{"val":4,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}}

Why it works

deserialize repeats the steps of serialize in the same order. Where serialize wrote a marker, deserialize takes one token and gives back no node. Where serialize wrote a value and two subtrees, deserialize makes a node and reads two subtrees. So each call uses exactly the tokens that one subtree produced.

Time and space

Time O(n), extra space O(n). Serializing writes one token for each node and one for each empty spot, n + 1 of them, and deserializing reads each token once: O(n) tokens and O(n) space. On a very deep tree the joined strings are copied at every level, which costs more than that.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not leave out the marker for a missing child. Without it, a root 1 with only a left child 2 and a root 1 with only a right child 2 both become 1,2.
• Values can be negative, so do not use "-" to separate the tokens. The tree -1 with left child 0 would be written -1-0-#-#-#, and splitting it gives an empty piece and 1 where -1 should be.
• Turn every value token back into a number. Left as text, the root of the first example comes back as "1" and not as the number 1, so the tree no longer equals the original.

Pattern

Preorder tree recursion. Builds on Encode and Decode Strings and Construct Binary Tree From Preorder And Inorder Traversal.

Keep going