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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Serialization Using Preorder Traversal

What is the output of the following serialization function when applied to the given binary tree?

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function serialize(root) {
  if (!root) return '#';
  return root.val + ',' + serialize(root.left) + ',' + serialize(root.right);
}

// Tree structure:
//     1
//    / \
//   2   3
//      / \
//     4   5

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

A 1,3,2,#,#,4,#,#,5,#,#

B 1,2,#,#,3,5,#,#,4,#,#

C 1,2,#,#,3,4,#,#,5,#,#

D 1,3,4,#,#,5,#,#,2,#,#

💡 Hint

Think about preorder traversal: root, left subtree, then right subtree. Null nodes are marked with '#'.

The serialize function uses preorder traversal. It visits root first, then left subtree, then right subtree. Null children are represented by '#'. So the output is "1,2,#,#,3,4,#,#,5,#,#".

❓ Predict Output

intermediate

Result of Deserializing a Serialized String

Given the deserialize function below, what will be the value of root.left.right after deserializing the string "1,2,#,3,#,#,4,#,#"?

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function deserialize(data) {
  const values = data.split(',');
  function helper() {
    if (values.length === 0) return null;
    const val = values.shift();
    if (val === '#') return null;
    const node = new TreeNode(parseInt(val));
    node.left = helper();
    node.right = helper();
    return node;
  }
  return helper();
}

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

A 3

B 4

C 2

D null

💡 Hint

Follow the recursive calls carefully and track the nodes created for each value.

The deserialization builds the tree in preorder. root is 1, root.left is 2, then root.left.left is null (#), root.left.right is 3, so root.left.right.val is 3.

🔧 Debug

advanced

Identify the Error in the Serialization Code

What error will the following serialization code produce when run on a binary tree?

DSA Javascript

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

// Note: returns null for empty nodes instead of '#'.

A Output string contains 'null' instead of '#' for empty nodes

B No error, outputs correct serialization string

C SyntaxError due to missing return statement

D TypeError: Cannot read property 'val' of null

💡 Hint

Check what happens when root is null and how it is represented in the output string.

The function returns null for empty nodes, so the output string will contain 'null' instead of '#' to mark null nodes. This is not an error but changes the expected output format.

🚀 Application

advanced

Number of Nodes After Deserialization

After deserializing the string "10,5,#,#,15,12,#,#,20,#,#" using the standard preorder deserialize function, how many nodes does the resulting binary tree have?

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function deserialize(data) {
  const values = data.split(',');
  function helper() {
    if (values.length === 0) return null;
    const val = values.shift();
    if (val === '#') return null;
    const node = new TreeNode(parseInt(val));
    node.left = helper();
    node.right = helper();
    return node;
  }
  return helper();
}

const root = deserialize("10,5,#,#,15,12,#,#,20,#,#");

function countNodes(root) {
  if (!root) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

console.log(countNodes(root));

A 4

B 7

C 6

D 5

💡 Hint

Count each non-null node created during deserialization.

The tree nodes are 10, 5, 15, 12, and 20. Total 5 nodes.

🧠 Conceptual

expert

Why Use '#' in Serialization of Binary Trees?

Why is the character '#' commonly used to represent null nodes in binary tree serialization?

A To reduce the size of the serialized string by replacing nulls with a single character

B To explicitly mark null children so the tree structure can be uniquely reconstructed

C Because '#' is the only character not allowed in node values

D To indicate the end of the serialized string

💡 Hint

Think about how the deserialization function knows where left and right children end.

Using '#' marks null children explicitly, allowing the deserialization to know exactly where subtrees end and reconstruct the tree uniquely.

Practice

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

easy

A. Sort the nodes of a binary tree in ascending order

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

C. Calculate the height of a binary tree

D. Delete all nodes in a binary tree

Solution

1. Step 1: Understand serialization

   Serialization means converting a data structure like a binary tree into a string format that can be stored or transmitted.

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 B

4. Quick Check:

   Serialize/deserialize = convert tree to/from string [OK]

Hint: Think of saving and loading a tree as text [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare a function in JavaScript for serializing a binary tree?

easy

A. function: serialize(root) { /* code */ }

B. serialize function(root) { /* code */ }

C. def serialize(root): { /* code */ }

D. function serialize(root) { /* code */ }

Solution

1. Step 1: Recall JavaScript function syntax

   In JavaScript, functions are declared using the keyword function followed by the name and parameters.

2. Step 2: Check each option

   function serialize(root) { /* code */ } uses correct syntax. Options A, B, and D use invalid or other language syntax.

3. Final Answer:

   function serialize(root) { /* code */ } -> Option D

4. Quick Check:

   JS function declaration = function name(params) [OK]

Hint: Use 'function name(params)' to declare in JS [OK]

Common Mistakes:

• Using Python or other language syntax
• Missing the 'function' keyword
• Using colons or wrong punctuation

3. What will be the output of the following code snippet?

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function serialize(root) {
  if (!root) return '#';
  return root.val + ',' + serialize(root.left) + ',' + serialize(root.right);
}

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(serialize(root));

medium

A. "1,2,#,#,3,#,#"

B. "1,2,3,#,#,#,#"

C. "1,#,2,#,3,#,#"

D. "#,#,1,2,3"

Solution

1. Step 1: Understand the serialize function

   The function uses preorder traversal: root, left, right. Null nodes are represented by '#'.

2. Step 2: Trace the tree serialization

   Root is 1, left child 2 (with no children), right child 3 (with no children). So serialization is "1,2,#,#,3,#,#".

3. Final Answer:

   "1,2,#,#,3,#,#" -> Option A

4. Quick Check:

   Preorder with '#' for null = "1,2,#,#,3,#,#" [OK]

Hint: Preorder traversal with '#' for null nodes [OK]

Common Mistakes:

• Confusing preorder with inorder or postorder
• Forgetting to add '#' for null children
• Mixing order of nodes in output

4. Identify the error in the following deserialize function for a binary tree:

function deserialize(data) {
  const values = data.split(',');
  function build() {
    if (values.length === 0) return null;
    const val = values.shift();
    if (val === '#') return null;
    const node = new TreeNode(val);
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

medium

A. The TreeNode constructor should convert val to number

B. The function does not handle empty input string

C. The values array should be reversed before processing

D. The function should use pop() instead of shift()

Solution

1. Step 1: Analyze the deserialize function

   The function splits the string and uses shift() to get values in order, which is correct.

2. Step 2: Check TreeNode value type

   Values from split are strings. If TreeNode expects numbers, val should be converted using Number(val) or +val.

3. Final Answer:

   The TreeNode constructor should convert val to number -> Option A

4. Quick Check:

   Convert string to number for node values [OK]

Hint: Convert string values to numbers when creating nodes [OK]

Common Mistakes:

• Ignoring type conversion of node values
• Reversing array unnecessarily
• Using pop() breaks preorder order

5. Given the serialized string "1,2,#,#,3,4,#,#,5,#,#", which of the following binary trees is the correct deserialized structure?

hard

A. Root 1 with left child 3, right child 2 with children 4 and 5

B. Root 1 with left child 2 with children 4 and 5, right child 3 (no children)

C. Root 1 with left child 2 (no children), right child 3 with left 4 and right 5

D. Root 1 with left child 4, right child 5 with children 2 and 3

Solution

1. Step 1: Understand the serialized string format

   The string uses preorder traversal with '#' for nulls: root, left subtree, right subtree.

2. Step 2: Trace the tree structure

   Root is 1, left child 2 with no children (#,#), right child 3 with left child 4 (no children) and right child 5 (no children).

3. Final Answer:

   Root 1 with left child 2 (no children), right child 3 with left 4 and right 5 -> Option C

4. Quick Check:

   Preorder string matches tree structure in Root 1 with left child 2 (no children), right child 3 with left 4 and right 5 [OK]

Hint: Draw preorder steps to visualize tree structure [OK]

Common Mistakes:

• Mixing left and right children
• Ignoring '#' as null nodes
• Misreading preorder order