Serialize and Deserialize Binary Tree in DSA Javascript - Execution Trace

Concept Flow - Serialize and Deserialize Binary Tree

Start Serialization

↓

Visit Node

↓

Serialize Left

↓

Add Node Value or Null

↓

Repeat for all nodes

↓

End Serialization

↓

Start Deserialization

↓

Read Next Value

↓

If value is null -> return null

↓

Create Node

↓

Deserialize Left

↓

Repeat for all values

↓

End Deserialization

Serialization visits each node and records its value or null for missing nodes. Deserialization reads values and rebuilds the tree recursively.

Execution Sample

DSA Javascript

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

function deserialize(data) {
  const nodes = data.split(',');
  function build() {
    const val = nodes.shift();
    if (val === 'null' || val === '') return null;
    const node = { val: Number(val), left: build(), right: build() };
    return node;
  }
  return build();
}

This code converts a binary tree to a string and back using preorder traversal with 'null' placeholders.

Execution Table

Step	Operation	Nodes in Tree (Preorder)	Pointer Changes	Visual State
1	Serialize root node (1)	1	root -> 1	1
2	Serialize left child (2)	1 -> 2	current -> 2	1 / 2
3	Serialize left child of 2 (null)	1 -> 2 -> null	current -> null	1 / 2 / null
4	Serialize right child of 2 (null)	1 -> 2 -> null -> null	current -> null	1 / 2 / null null
5	Serialize right child (3)	1 -> 2 -> null -> null -> 3	current -> 3	1 / 2 3 / null null
6	Serialize left child of 3 (4)	1 -> 2 -> null -> null -> 3 -> 4	current -> 4	1 / 2 3 / 4 null
7	Serialize left child of 4 (null)	1 -> 2 -> null -> null -> 3 -> 4 -> null	current -> null	1 / 2 3 / 4 null / null
8	Serialize right child of 4 (null)	1 -> 2 -> null -> null -> 3 -> 4 -> null -> null	current -> null	1 / 2 3 / 4 null / null null
9	Serialize right child of 3 (null)	1 -> 2 -> null -> null -> 3 -> 4 -> null -> null -> null	current -> null	1 / 2 3 / 4 null null / null null
10	Deserialization starts		nodes array reset
11	Read value '1', create node 1	1	root -> 1	1
12	Read value '2', create left child	1 -> 2	current -> 2	1 / 2
13	Read value 'null', left child of 2 is null	1 -> 2 -> null	current -> null	1 / 2 / null
14	Read value 'null', right child of 2 is null	1 -> 2 -> null -> null	current -> null	1 / 2 / null null
15	Read value '3', create right child	1 -> 2 -> null -> null -> 3	current -> 3	1 / 2 3 / null null
16	Read value '4', create left child of 3	1 -> 2 -> null -> null -> 3 -> 4	current -> 4	1 / 2 3 / 4 null
17	Read value 'null', left child of 4 is null	1 -> 2 -> null -> null -> 3 -> 4 -> null	current -> null	1 / 2 3 / 4 null / null
18	Read value 'null', right child of 4 is null	1 -> 2 -> null -> null -> 3 -> 4 -> null -> null	current -> null	1 / 2 3 / 4 null / null null
19	Read value 'null', right child of 3 is null	1 -> 2 -> null -> null -> 3 -> 4 -> null -> null -> null	current -> null	1 / 2 3 / 4 null null / null null
20	Deserialization complete	Tree rebuilt	root returned	1 / 2 3 / 4 null null / null null

💡 All nodes processed; serialization and deserialization complete

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
Serialized String	""	"1,"	"1,2,"	"1,2,null,"	"1,2,null,null,"	"1,2,null,null,3,"	"1,2,null,null,3,4,"	"1,2,null,null,3,4,null,"	"1,2,null,null,3,4,null,null,"	"1,2,null,null,3,4,null,null,null,"	"1,2,null,null,3,4,null,null,null,"	"1,2,null,null,3,4,null,null,null,"
Deserialization Nodes Array	[]	["1","2","null","null","3","4","null","null","null",""]	["2","null","null","3","4","null","null","null",""]	["null","null","3","4","null","null","null",""]	["null","3","4","null","null","null",""]	["3","4","null","null","null",""]	["4","null","null","null",""]	["null","null","null",""]	["null","null",""]	["null",""]	[""]	[]
Current Node	null	1	2	null	null	3	4	null	null	null	null	null

Key Moments - 3 Insights

Why do we add 'null' strings during serialization?

The 'null' strings represent missing children so the tree structure can be fully reconstructed during deserialization, as shown in steps 3, 4, 7, 8, 9 in the execution_table.

How does deserialization know when to stop creating nodes?

Deserialization stops creating nodes when it reads a 'null' value from the serialized data, returning null for that child, as seen in steps 13, 14, 17, 18, 19.

Why do we use preorder traversal for serialization?

Preorder traversal records the root before its children, allowing deserialization to rebuild the tree top-down correctly, as the execution_table shows visiting root first then left and right.

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What node is currently being serialized?

A Node with value 3

B Node with value 4

C Null node

D Node with value 2

💡 Hint

Check the 'Operation' and 'Nodes in Tree' columns at step 6 in execution_table

At which step does deserialization create the left child of node 3?

A Step 15

B Step 16

C Step 17

D Step 18

💡 Hint

Look for 'create left child of 3' in the 'Operation' column of execution_table

If we remove all 'null' entries from the serialized string, what will happen during deserialization?

A Deserialization will fail to reconstruct the tree correctly

B Deserialization will succeed without issues

C The tree will be serialized with extra nodes

D The serialized string will be shorter but correct

💡 Hint

Refer to key_moments about why 'null' placeholders are needed

Concept Snapshot

Serialize: Traverse tree preorder, record node values and 'null' for missing nodes.
Deserialize: Read values in order, create nodes or nulls recursively.
Use commas to separate values.
Preorder ensures root is first, enabling correct tree rebuild.
'null' placeholders keep tree shape intact.

Full Transcript

Serialization of a binary tree means converting it into a string that records each node's value and uses 'null' for missing children. This is done using preorder traversal: visit root, then left subtree, then right subtree. Deserialization reads this string and rebuilds the tree by creating nodes or nulls in the same order. The execution table shows each step of serialization adding values or 'null' to the string, and deserialization reading these values to reconstruct the tree. Key moments clarify why 'null' is necessary to keep the tree shape and why preorder traversal is used. The visual quiz tests understanding of these steps and the importance of 'null' placeholders.

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