Serialize and Deserialize Binary Tree in DSA Javascript - Build from Scratch

Serialize and Deserialize Binary Tree

📖 Scenario: Imagine you are working on a messaging app that needs to send a family tree structure over the internet. To do this, you need to convert the tree into a string format to send it, and then convert it back to the tree structure on the other side.

🎯 Goal: You will build two functions: one to convert a binary tree into a string (serialize), and another to convert that string back into the original binary tree (deserialize).

📋 What You'll Learn

Create a binary tree node class called TreeNode with val, left, and right properties.

Write a function called serialize that converts a binary tree into a string using preorder traversal.

Write a function called deserialize that converts the string back into the original binary tree.

Use null to represent empty nodes in the serialized string.

Print the serialized string and verify the deserialized tree structure.

💡 Why This Matters

🌍 Real World

Serialization and deserialization are used to save and transfer complex data structures like trees in databases, files, or over networks.

💼 Career

Understanding how to serialize and deserialize data structures is important for backend development, data engineering, and working with APIs or distributed systems.

1

Create the Binary Tree Node Class

Create a class called TreeNode with a constructor that takes a parameter val and sets this.val to val, this.left to null, and this.right to null.

DSA Javascript

// Your code here

Hint

Think of each node as a person in the family tree with a value and links to left and right children.

2

Create a Sample Binary Tree

Create a binary tree by creating a root node called root with value 1. Then set root.left to a new TreeNode with value 2, and root.right to a new TreeNode with value 3. Finally, set root.right.left to a new TreeNode with value 4 and root.right.right to a new TreeNode with value 5.

DSA Javascript

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

// Your code here

Hint

Build the tree step by step by linking nodes as left and right children.

3

Write the Serialize and Deserialize Functions

Write a function called serialize that takes a root node and returns a string representing the tree using preorder traversal. Use null for empty nodes. Then write a function called deserialize that takes the string and reconstructs the original tree. Use a helper array to process nodes in order.

DSA Javascript

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

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(5);

// Write serialize and deserialize functions below
// Your code here

Hint

Use preorder traversal: visit node, then left, then right. Use recursion for both serialize and deserialize.

4

Print the Serialized String and Verify Deserialization

Print the serialized string of the root tree by calling serialize(root). Then deserialize the string back to a tree using deserialize. Finally, print the value of the root node of the deserialized tree.

DSA Javascript

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

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(5);

function serialize(root) {
    const result = [];
    function helper(node) {
        if (node === null) {
            result.push('null');
            return;
        }
        result.push(String(node.val));
        helper(node.left);
        helper(node.right);
    }
    helper(root);
    return result.join(',');
}

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

// Print serialized string and root value of deserialized tree
// Your code here

Hint

The serialized string should show the preorder traversal with 'null' for empty nodes. The deserialized root value should be 1.

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