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.