Skip to main content

25. Serialize and Deserialize Binary Tree

hardAsked at Coursera

Design an algorithm to serialize and deserialize a binary tree, a systems-design coding problem Coursera uses to test encoding/decoding logic relevant to course content persistence.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree structure. The encoded string should be decodable back to exactly the same tree.

Constraints

  • Number of nodes in the tree is in the range [0, 10^4]
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [1,2,3,null,null,4,5]
Output
[1,2,3,null,null,4,5] (round-trip)

Example 2

Input
root = []
Output
[]

Approaches

1. BFS level-order (JSON array)

Use level-order traversal to produce a JSON array with null for missing nodes — matches LeetCode format but produces longer strings with many nulls for sparse trees.

Time
O(n)
Space
O(n)
// BFS encode — produces [1,2,3,null,null,4,5]
// Decode: reconstruct from level-order array
// Verbose; skip for brevity

Tradeoff:

2. DFS preorder with null markers

Preorder DFS encodes node values separated by commas with 'N' for null leaves. Decoding consumes a pointer into a split array, recursively reconstructing the tree in the same preorder sequence.

Time
O(n)
Space
O(n)
const serialize = root => {
  if (!root) return 'N';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
};
const deserialize = data => {
  const vals = data.split(',');
  let i = 0;
  function build() {
    if (vals[i] === 'N') { i++; return null; }
    const node = new TreeNode(+vals[i++]);
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
};

Tradeoff:

Coursera-specific tips

Coursera interviews emphasize algorithms for educational platforms, content recommendation systems, and scalable delivery pipelines. Medium-difficulty graph and DP problems are typical.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

More Coursera coding interview questions

See all Coursera problems →

Companies that also ask Serialize and Deserialize Binary Tree