Serialize and Deserialize Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Serialize and Deserialize Binary Tree

Start Serialization

↓

Visit Node

↓

Serialize Left

↓

Add Node Value or Null

↓

Repeat Until All Nodes

↓

Output Serialized String

↓

Start Deserialization

↓

Read Next Value

↓

If Null -> Return null

↓

Create Node

↓

Deserialize Left

↓

Return Node

↓

Repeat Until String Ends

Serialization visits each node in preorder, recording values or nulls; deserialization reads values to rebuild the tree recursively.

Execution Sample

DSA Typescript

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

function deserialize(data: string): TreeNode | null {
  const nodes = data.split(',');
  function build(): TreeNode | null {
    const val = nodes.shift();
    if (val === 'null' || val === undefined || val === '') return null;
    const node = new TreeNode(parseInt(val));
    node.left = build();
    node.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	Node Visited	Pointer Changes	Serialized String / Tree State
1	Serialize root node	1	root	Serialized: '1,'
2	Serialize left child	2	root.left	Serialized: '1,2,'
3	Serialize left.left (null)	null	-	Serialized: '1,2,null,'
4	Serialize left.right (null)	null	-	Serialized: '1,2,null,null,'
5	Serialize right child	3	root.right	Serialized: '1,2,null,null,3,'
6	Serialize right.left (null)	null	-	Serialized: '1,2,null,null,3,null,'
7	Serialize right.right (null)	null	-	Serialized: '1,2,null,null,3,null,null,'
8	Deserialization start	-	-	Input: '1,2,null,null,3,null,null,'
9	Create root node	1	root	Tree: 1
10	Create left child	2	root.left	Tree: 1 -> 2 (left)
11	Left.left is null	null	-	Tree unchanged
12	Left.right is null	null	-	Tree unchanged
13	Create right child	3	root.right	Tree: 1 -> 3 (right)
14	Right.left is null	null	-	Tree unchanged
15	Right.right is null	null	-	Tree unchanged
16	Deserialization complete	-	-	Tree rebuilt: 1 -> 2 (left), 3 (right)

💡 All nodes visited and serialized; all values consumed and tree rebuilt.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
Serialized String	''	'1,'	'1,2,'	'1,2,null,'	'1,2,null,null,'	'1,2,null,null,3,'	'1,2,null,null,3,null,'	'1,2,null,null,3,null,null,'
Deserialization nodes array	['1','2','null','null','3','null','null','']	['2','null','null','3','null','null','']	['null','null','3','null','null','']	['null','3','null','null','']	['3','null','null','']	['null','null','']	['null','']	['']
Current Node	null	1	2	null	null	3	null	null

Key Moments - 3 Insights

Why do we add 'null' for empty children during serialization?

Adding 'null' placeholders ensures the tree structure is preserved exactly, as shown in steps 3, 4, 6, and 7 in the execution_table where nulls mark missing children.

How does deserialization know when to stop creating nodes?

Deserialization reads 'null' values to return null nodes, stopping recursion as seen in steps 11, 12, 14, and 15 where 'null' causes return without creating nodes.

Why do we use preorder traversal for serialization?

Preorder visits root before children, allowing deserialization to reconstruct the tree in the same order, matching the sequence in the serialized string from steps 1 to 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the serialized string after serializing the right child?

A '1,2,null,null,3,'

B '1,2,null,null,'

C '1,2,null,null,3,null,'

D '1,2,null,null,3,null,null,'

💡 Hint

Check the Serialized String column at step 5 in execution_table.

At which step does deserialization create the left child node?

A Step 9

B Step 10

C Step 13

D Step 11

💡 Hint

Look at the Operation and Node Visited columns in execution_table for deserialization steps.

If we remove 'null' placeholders during serialization, what will happen during deserialization?

A Deserialization will work correctly without changes

B The serialized string will be longer

C Deserialization will fail to rebuild the exact tree structure

D The tree will have extra nodes

💡 Hint

Refer to key_moments about why 'null' placeholders are needed.

Concept Snapshot

Serialize: preorder traversal, record node values and 'null' for empty children.
Deserialize: read values in order, create nodes or nulls recursively.
'null' placeholders keep tree shape exact.
Preorder ensures root is first, aiding reconstruction.
Use split and shift on string for deserialization.
Simple, recursive, and reversible process.

Full Transcript

Serialization of a binary tree uses preorder traversal to visit each node. For each node, its value is recorded followed by serializing its left and right children. If a child is missing, 'null' is recorded to keep the tree shape. This process creates a string representing the tree structure. Deserialization reads this string from left to right, creating nodes or nulls recursively in preorder. This rebuilds the original tree exactly. The execution table shows each step of serialization and deserialization, tracking the serialized string and tree state. Key moments clarify why 'null' placeholders are essential and why preorder traversal is used. The visual quiz tests understanding of these steps and their effects. This method is simple, reliable, and widely used for tree data transfer.

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