Serialize and Deserialize Binary Tree

1. Define the problem

Serialize and Deserialize Binary Tree

Write two halves of one idea. Serializing turns a binary tree into a single text string . Deserializing turns that string back into the exact same tree . This is how a tree gets saved to a file or sent over a network. A pre-order walk works well: write the node, then its left side, then its right side, and write a marker for every empty spot . Those markers are what make the string readable back: without them you cannot tell where one side ends. The tree arrives as a level-order array such as [1, 2, 3, null, null, 4, 5], with null for a missing child. Your function builds the tree, serializes it, deserializes that string into a fresh tree, and returns the string produced from that fresh tree. If both halves are correct, the round trip gives the same string back.

Constraints

The number of nodes is between 0 and 10⁴
-1000 ≤ node value ≤ 1000
Input is a level-order array with null for a missing child
Return the serialized string; an empty tree serializes to "#"

Example

Inputvalues = [1, 2, 3, null, null, 4, 5]

Output'1,2,#,#,3,4,#,#,5,#,#'

Explanation Writing the tree in pre-order gives 1, then its left child 2 with two empty spots, then its right child 3, whose children 4 and 5 each contribute a value and two empty spots. Reading those tokens back in the same order rebuilds the identical tree.

2. Know the words first

In plain terms

Serialize: Turn a structure held in memory into a flat sequence of characters that can be stored or sent somewhere else.
Deserialize: Read such a sequence of characters back and rebuild the original structure from it.
Pre-order walk: Visit the node itself first, then everything on its left, then everything on its right. Writing a tree this way lets you rebuild it by reading the tokens in the same order.
Marker: A stand-in character written where a child is missing. Here it is #, and it is what tells the rebuilder to stop going deeper and come back up.

3. Visualize the solution

One cell per token of the serialized string, in the order the tokens are written

t0—

t1—

t2—

t3—

t4—

t5—

t6—

Statusinit

The tree [1, 2, 3] will produce seven tokens, none written yet.

What happens in this step

values = [1, 2, 3]

The tree is a root 1 with children 2 and 3.
Three real nodes plus four empty spots means
seven tokens in total.

parts = []

Step 1 of 7

Steps to visualize

Each cell is one token of the output string, written left to right as the walk proceeds.
A number token means a real node; a # token means an empty spot.
The walk always writes the node first, then everything on its left, then everything on its right.
Deserializing reads the very same tokens in the very same order, so the tree comes back unchanged.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per token of the serialized string, in the order the tokens are written

t0—

t1—

t2—

t3—

t4—

t5—

t6—

Statusinit

The tree [1, 2, 3] will produce seven tokens, none written yet.

What happens in this step

values = [1, 2, 3]

The tree is a root 1 with children 2 and 3.
Three real nodes plus four empty spots means
seven tokens in total.

parts = []

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function serializeAndDeserialize(values) {
  function Node(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  function serialize(root) {
    const parts = [];

    function walk(current) {
      if (current === null) {
        parts.push('#');
        return;
      }

      parts.push(String(current.val));
      walk(current.left);
      walk(current.right);
    }

    walk(root);

    return parts.join(',');
  }

  function deserialize(text) {
    const parts = text.split(',');
    let index = 0;

    function rebuild() {
      const token = parts[index];
      index += 1;

      if (token === '#') {
        return null;
      }

      const node = new Node(Number(token));
      node.left = rebuild();
      node.right = rebuild();

      return node;
    }

    return rebuild();
  }

  const text = serialize(buildTree(values));

  return serialize(deserialize(text));
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`values = [1, 2, 3, null, null, 4, 5]`	`'1,2,#,#,3,4,#,#,5,#,#'`	example from the docstring
`values = []`	`'#'`	an empty tree is a single marker
`values = [1]`	`'1,#,#'`	one node with two empty spots
`values = [1, 2]`	`'1,2,#,#,#'`	a lone left child
`values = [1, null, 2]`	`'1,#,2,#,#'`	a lone right child, which the markers keep distinct from a left child
`values = [1, 2, 3]`	`'1,2,#,#,3,#,#'`	the tree used in the step-by-step walkthrough

Serialize and Deserialize Binary Tree