Serialize and Deserialize Binary Tree in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Preorder Serialization

What is the output of the following TypeScript code that serializes a binary tree using preorder traversal with 'null' for empty nodes?

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;
  }
}

function serialize(root: TreeNode | null): string {
  if (!root) return 'null';
  return root.val + ',' + serialize(root.left) + ',' + serialize(root.right);
}

const tree = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
console.log(serialize(tree));

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

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

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

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

💡 Hint

Think about preorder traversal: root, left subtree, then right subtree. Use 'null' for missing children.

The serialization uses preorder traversal. For each node, it records the value, then recursively serializes the left and right children. Null children are represented as 'null'. The output string is a comma-separated list of values and 'null's.

❓ Predict Output

intermediate

Result of Deserializing a Serialized Tree

Given the serialized string "1,2,null,null,3,4,null,null,5,null,null", what is the value of the root's right child's left child after deserializing with the code below?

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;
  }
}

function deserialize(data: string): TreeNode | null {
  const list = data.split(',');
  function helper(): TreeNode | null {
    if (list.length === 0) return null;
    const val = list.shift();
    if (val === 'null') return null;
    const node = new TreeNode(Number(val));
    node.left = helper();
    node.right = helper();
    return node;
  }
  return helper();
}

const root = deserialize("1,2,null,null,3,4,null,null,5,null,null");
console.log(root?.right?.left?.val);

A 4

B 5

C 3

D null

💡 Hint

Trace the deserialization step by step, matching nodes to values in preorder.

The deserialization reconstructs the tree in preorder. The root's right child is 3, and its left child is 4, so the output is 4.

🔧 Debug

advanced

Identify the Error in Serialization Code

What error does the following TypeScript serialization code produce when run on a non-empty tree?

DSA Typescript

function serialize(root: TreeNode | null): string {
  if (!root) return '';
  return root.val + ',' + serialize(root.left) + ',' + serialize(root.right);
}

const tree = new TreeNode(1, new TreeNode(2), null);
console.log(serialize(tree));

A SyntaxError due to missing return type

B The output string has extra commas and missing 'null' for empty nodes

C TypeError because root.val is undefined

D Runtime error due to infinite recursion

💡 Hint

Consider what happens when a child node is null and how it is represented in the output string.

The code returns an empty string for null nodes instead of 'null'. This causes missing markers for empty nodes and extra commas in the output string, which can cause problems during deserialization.

🚀 Application

advanced

Number of Nodes After Deserialization

After deserializing the string "1,2,null,null,3,null,4,null,null" using the standard preorder deserialization method, how many nodes does the resulting binary tree contain?

DSA Typescript

function deserialize(data: string): TreeNode | null {
  const list = data.split(',');
  function helper(): TreeNode | null {
    if (list.length === 0) return null;
    const val = list.shift();
    if (val === 'null') return null;
    const node = new TreeNode(Number(val));
    node.left = helper();
    node.right = helper();
    return node;
  }
  return helper();
}

const root = deserialize("1,2,null,null,3,null,4,null,null");

A 5

B 3

C 6

D 4

💡 Hint

Count nodes by tracing the preorder deserialization and ignoring 'null' markers.

The tree has nodes with values 1, 2, 3, and 4. Nulls mark missing children. So total nodes are 4.

🧠 Conceptual

expert

Why Use 'null' Markers in Serialization?

Why is it important to include explicit 'null' markers for empty nodes when serializing a binary tree using preorder traversal?

A To preserve the exact tree structure including missing children during deserialization

B To reduce the size of the serialized string by skipping empty nodes

C To make the serialization compatible with inorder traversal

D To allow the tree to be serialized without recursion

💡 Hint

Think about what happens if you omit empty nodes in the serialized data.

Null markers are needed to know where children are missing, so the tree can be rebuilt exactly as it was. Without them, the structure is lost.

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