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

Serialize and Deserialize Binary Tree

📖 Scenario: Imagine you are building a system that needs to save and load family trees. Each family tree is a binary tree where each person has up to two children. To save the tree to a file or send it over the network, you need to convert it into a string (serialize). Later, you want to rebuild the exact same tree from that string (deserialize).

🎯 Goal: You will create two functions: one to convert a binary tree into a string, and another to convert that string back into the original binary tree. This will help you save and load family trees easily.

📋 What You'll Learn

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

Create a function serialize that converts a binary tree into a string using preorder traversal and uses 'null' for empty nodes.

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

Test the functions with a sample tree and print the serialized string and the root node's value after deserialization.

💡 Why This Matters

🌍 Real World

Saving and loading complex data structures like family trees, decision trees, or game states in a format that can be stored or sent over a network.

💼 Career

Understanding serialization and deserialization is important for backend development, data storage, network communication, and working with APIs.

1

Create the TreeNode class and sample tree

Define a class called TreeNode with a constructor that takes a number val and optional left and right nodes. Then create a sample tree with root value 1, left child 2, and right child 3 where 3 has children 4 and 5.

DSA Typescript

// Define TreeNode class and create sample tree
// Your code here

Hint

Remember to set left and right to null by default in the constructor.

2

Create the serialize function

Write a function called serialize that takes a TreeNode | null called root and returns a string. Use preorder traversal (root, left, right). Represent null nodes as the string 'null'. Separate values with commas.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

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

const root = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3, new TreeNode(4), new TreeNode(5))
);

function serialize(root: TreeNode | null): string {
    // Your code here
}

Hint

Use a recursive function that returns 'null' for empty nodes and concatenates values with commas.

3

Create the deserialize function

Write a function called deserialize that takes a string data and returns a TreeNode | null. Split the string by commas into an array. Use a helper function that reads the next value, returns null if it is 'null', or creates a TreeNode and recursively builds left and right children.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

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

const root = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3, new TreeNode(4), new TreeNode(5))
);

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

function deserialize(data: string): TreeNode | null {
    // Your code here
}

Hint

Use a recursive helper function that reads values one by one from the array and builds the tree.

4

Test serialization and deserialization

Call serialize with the root tree and store the result in data. Then call deserialize with data and store the result in newRoot. Finally, print data and newRoot.val.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

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

const root = new TreeNode(1,
    new TreeNode(2),
    new TreeNode(3, new TreeNode(4), new TreeNode(5))
);

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

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

const data = serialize(root);
const newRoot = deserialize(data);

// Your code here

Hint

Print the serialized string and the value of the root node of the deserialized tree.

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