Serialize and Deserialize Binary Tree in DSA Typescript

Mental Model

We turn a tree into a string to save or send it, then rebuild the exact same tree from that string.

Analogy: Like writing a family tree on paper and later using that paper to redraw the same family tree exactly as it was.

    1
   / \
  2   3
     / \
    4   5

Serialize as: "1,2,null,null,3,4,null,null,5,null,null,"

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 3 has children 4 and 5

Goal: Convert the tree into a string and then rebuild the same tree from that string

Step 1: Start serialization at root node 1

Serialize: "1,"

Why: We record the root value first to start the string

Step 2: Serialize left subtree of 1 (node 2)

Serialize: "1,2,"

Why: We record left child value next

Step 3: Serialize left child of 2 which is null

Serialize: "1,2,null,"

Why: We mark null to remember no left child

Step 4: Serialize right child of 2 which is null

Serialize: "1,2,null,null,"

Why: We mark null to remember no right child

Step 5: Serialize right subtree of 1 (node 3)

Serialize: "1,2,null,null,3,"

Why: We record right child value after left subtree

Step 6: Serialize left child of 3 (node 4)

Serialize: "1,2,null,null,3,4,"

Why: We record left child of 3

Step 7: Serialize left and right children of 4 which are null

Serialize: "1,2,null,null,3,4,null,null,"

Why: Mark nulls for 4's children

Step 8: Serialize right child of 3 (node 5) and its null children

Serialize: "1,2,null,null,3,4,null,null,5,null,null,"

Why: Complete serialization with right subtree

Step 9: Start deserialization from string

Deserialize: reading "1" creates root node 1

Why: We rebuild root first

Step 10: Deserialize left subtree from next tokens "2,null,null"

Deserialize: node 2 with null children attached to root

Why: Rebuild left subtree exactly

Step 11: Deserialize right subtree from tokens "3,4,null,null,5,null,null"

Deserialize: node 3 with children 4 and 5 rebuilt

Why: Rebuild right subtree exactly

Result:

Final tree rebuilt exactly as original:
    1
   / \
  2   3
     / \
    4   5

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

class Codec {
  // Serialize tree to string
  serialize(root: TreeNode | null): string {
    if (root === null) return "null,"; // mark null nodes
    return root.val + "," + this.serialize(root.left) + this.serialize(root.right);
  }

  // Deserialize string to tree
  deserialize(data: string): TreeNode | null {
    const nodes = data.split(",");
    function helper(): TreeNode | null {
      const val = nodes.shift();
      if (val === "null" || val === undefined || val === "") return null; // null node found or empty string
      const node = new TreeNode(parseInt(val));
      node.left = helper(); // build left subtree
      node.right = helper(); // build right subtree
      return node;
    }
    return helper();
  }
}

// Driver code
const root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
const codec = new Codec();
const serialized = codec.serialize(root);
console.log("Serialized:", serialized);
const deserializedRoot = codec.deserialize(serialized);

// Helper to print tree inorder for verification
function inorderPrint(node: TreeNode | null): string {
  if (!node) return "null";
  return node.val + "(" + inorderPrint(node.left) + "," + inorderPrint(node.right) + ")";
}
console.log("Deserialized inorder:", inorderPrint(deserializedRoot));

if (root === null) return "null,";

mark null nodes explicitly to preserve tree shape

return root.val + "," + this.serialize(root.left) + this.serialize(root.right);

serialize current node then left and right subtrees recursively

const val = nodes.shift();

read next value from serialized data to rebuild node

if (val === "null" || val === undefined) return null;

detect null marker to stop recursion on this branch

node.left = helper();

rebuild left subtree recursively

node.right = helper();

rebuild right subtree recursively

Output

Serialized: 1,2,null,null,3,4,null,null,5,null,null,

Deserialized inorder: 1(2(null,null),3(4(null,null),5(null,null)))

Complexity Analysis

Time: O(n) because we visit each node once during serialization and once during deserialization

Space: O(n) for the recursion stack and the serialized string storing all nodes

vs Alternative: Compared to level-order serialization, preorder with null markers is simpler and uses recursion, but both have similar O(n) cost

Edge Cases

Empty tree (root is null)

Serialization returns "null," and deserialization returns null tree

DSA Typescript

if (root === null) return "null,";

Tree with only one node

Serialization returns "val,null,null," and deserialization rebuilds single node

DSA Typescript

if (val === "null" || val === undefined) return null;

Tree with only left or only right children

Null markers preserve missing children so tree shape is exact

DSA Typescript

if (val === "null" || val === undefined) return null;

When to Use This Pattern

When you need to save or send a tree structure and later rebuild it exactly, use serialize/deserialize with preorder traversal and null markers to preserve shape.

Common Mistakes

Mistake: Not marking null children during serialization, causing incorrect tree shape on deserialization
Fix: Always serialize null children explicitly as "null," to keep tree structure

Mistake: Using split without handling trailing commas causing empty strings in array
Fix: Ensure to handle or ignore empty strings after splitting serialized data

Summary

It converts a binary tree to a string and back to the same tree.

Use it when you want to save or transfer a tree and restore it later exactly.

The key is to record null children explicitly to keep the tree shape intact.

Practice

1. What is the main purpose of serialize and deserialize functions in the context of a binary tree?

easy

A. Find the height of the binary tree

B. Sort the binary tree nodes in ascending order

C. Convert a binary tree to a string and back to a binary tree

D. Delete all nodes in the binary tree

Solution

1. Step 1: Understand serialization

   Serialization means converting a binary tree into a string format that can be stored or sent.

2. Step 2: Understand deserialization

   Deserialization means converting the string back into the original binary tree structure.

3. Final Answer:

   Convert a binary tree to a string and back to a binary tree -> Option C

4. Quick Check:

   Serialize + Deserialize = Convert tree to string and back [OK]

Hint: Serialization means tree to string, deserialization reverses it [OK]

Common Mistakes:

• Confusing serialization with sorting
• Thinking deserialization deletes nodes
• Mixing serialization with tree height calculation

2. Which of the following TypeScript function signatures correctly represents a deserialize function for a binary tree?

easy

A. function deserialize(data: string): TreeNode | null

B. function deserialize(data: number): TreeNode

C. function deserialize(tree: TreeNode): string

D. function deserialize(): void

Solution

1. Step 1: Identify input and output types

   Deserialize takes a string (serialized data) and returns a TreeNode or null if empty.

2. Step 2: Match correct signature

   function deserialize(data: string): TreeNode | null matches input as string and output as TreeNode or null.

3. Final Answer:

   function deserialize(data: string): TreeNode | null -> Option A

4. Quick Check:

   Deserialize input string, output tree node [OK]

Hint: Deserialize input is string, output is tree node or null [OK]

Common Mistakes:

• Using number instead of string as input
• Returning string instead of tree node
• No input or void return type

3. Given the following serialized string of a binary tree using preorder with '#' as null marker: "1,2,#,#,3,4,#,#,5,#,#", what is the inorder traversal of the deserialized tree?

medium

A. [1, 2, 3, 4, 5]

B. [2, 1, 4, 3, 5]

C. [2, 4, 1, 3, 5]

D. [1, 3, 2, 4, 5]

Solution

1. Step 1: Reconstruct tree from preorder string

   Preorder: 1 (root), 2 (left), #,# (2's children null), 3 (right), 4 (3's left), #,# (4's children null), 5 (3's right), #,# (5's children null).

2. Step 2: Perform inorder traversal (left, root, right)

   Inorder: left subtree of 1 is 2, root 1, left subtree of 3 is 4, root 3, right subtree 5. So inorder is [2, 1, 4, 3, 5].

3. Final Answer:

   [2, 1, 4, 3, 5] -> Option B

4. Quick Check:

   Preorder string to tree, inorder traversal = [2,1,4,3,5] [OK]

Hint: Rebuild tree from preorder, then do inorder traversal [OK]

Common Mistakes:

• Confusing preorder with inorder
• Misplacing null markers
• Incorrect traversal order

4. Consider this deserialize function snippet in TypeScript:

function deserialize(data: string): TreeNode | null {
  const values = data.split(",");
  function build(): TreeNode | null {
    if (!values.length) return null;
    const val = values.shift();
    if (val === "#") return null;
    const node = new TreeNode(parseInt(val));
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

What is the bug in this code if the input string is empty?

medium

A. It returns null correctly, no bug

B. parseInt throws error on undefined

C. The function build never terminates

D. parseInt('') returns NaN, creating invalid TreeNode

Solution

1. Step 1: Check behavior on empty input

   If data is empty string, values = [""], so values.length is 1, not zero.

2. Step 2: Analyze values.shift() and val check

   values.shift() returns "" (empty string), val === "#" is false, parseInt("") returns NaN, which may cause issues when creating TreeNode.

3. Step 3: Identify actual bug

   parseInt("") returns NaN, so TreeNode is created with NaN value, which is likely unintended.

4. Final Answer:

   parseInt('') returns NaN, creating invalid TreeNode -> Option D

5. Quick Check:

   Empty input leads to undefined or NaN node value [OK]

Hint: Empty string splits to [''], not empty array; check val before parseInt [OK]

Common Mistakes:

• Assuming empty string splits to empty array
• Ignoring parseInt('') returns NaN
• Thinking function never ends

5. You want to serialize a binary tree using level-order traversal (BFS) with 'null' for missing nodes. Which of these serialized strings correctly represents the tree:

Tree:
1
/ \ 2 3
/ \ 4 5

Options:

hard

A. "1,2,3,null,null,4,5,null,null,null,null"

B. "1,2,3,4,5,null,null,null,null,null,null"

C. "1,3,2,null,4,5,null,null,null,null,null"

D. "1,2,3,4,null,5,null,null,null,null,null"

Solution

1. Step 1: Understand level-order traversal

   Level order visits nodes level by level: root, then children left to right, including nulls for missing nodes.

2. Step 2: Write level order for given tree

   Level 1: 1
   Level 2: 2, 3
   Level 3: null, null (2's children), 4, 5 (3's children)
   Level 4: nulls for 4 and 5's children
   So serialized string is "1,2,3,null,null,4,5,null,null,null,null".

3. Final Answer:

   "1,2,3,null,null,4,5,null,null,null,null" -> Option A

4. Quick Check:

   Level order with nulls matches "1,2,3,null,null,4,5,null,null,null,null" [OK]

Hint: Level order includes nulls for missing children [OK]

Common Mistakes:

• Mixing preorder with level order
• Omitting null placeholders
• Swapping left and right children