Serialize and Deserialize Binary Tree in DSA Javascript

Mental Model

We turn a tree into a string to save or send it, then rebuild the exact tree from that string.

Analogy: Like writing a family tree on paper and later using that paper to redraw the same family tree exactly.

    1
   / \
  2   3
     / \
    4   5

Serialize as: "1,2,null,null,3,4,null,null,5,null,null"

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 3 has children 4 and 5

Goal: Convert the tree to a string and then rebuild the exact same tree from that string

Step 1: Start serialization at root node 1

Serialize string: "1"

Why: We record the root value first to start the string

Step 2: Serialize left child 2

Serialize string: "1,2"

Why: We add left subtree values next to keep order

Step 3: Serialize left and right children of 2 which are null

Serialize string: "1,2,null,null"

Why: We add nulls to mark no further children for node 2

Step 4: Serialize right child 3

Serialize string: "1,2,null,null,3"

Why: After left subtree, we serialize right subtree root

Step 5: Serialize left child 4 of node 3

Serialize string: "1,2,null,null,3,4"

Why: Continue preorder traversal to left child of 3

Step 6: Serialize null children of 4

Serialize string: "1,2,null,null,3,4,null,null"

Why: Mark leaf node 4's children as null

Step 7: Serialize right child 5 of node 3

Serialize string: "1,2,null,null,3,4,null,null,5"

Why: Move to right child of 3

Step 8: Serialize null children of 5

Serialize string: "1,2,null,null,3,4,null,null,5,null,null"

Why: Mark leaf node 5's children as null

Step 9: Start deserialization from string

Tokens: [1,2,null,null,3,4,null,null,5,null,null]

Why: We split string to rebuild tree nodes in order

Step 10: Create node 1, then recursively create left subtree from next tokens

Tree root: 1 with left subtree starting at 2

Why: Rebuild tree top-down matching serialization order

Step 11: Create node 2, then assign null children

Left child of 1 is 2 with no children

Why: Leaf node 2 reconstructed with null children

Step 12: Create node 3 as right child of 1, then build its children

Right child of 1 is 3 with children 4 and 5

Why: Rebuild right subtree fully

Step 13: Create node 4 with null children

Left child of 3 is 4 with no children

Why: Leaf node 4 reconstructed

Step 14: Create node 5 with null children

Right child of 3 is 5 with no children

Why: Leaf node 5 reconstructed

Result:

Tree rebuilt exactly as:
    1
   / \
  2   3
     / \
    4   5

Annotated Code

DSA Javascript

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

function serialize(root) {
  if (root === null) return 'null';
  // serialize current node value
  const leftSerialized = serialize(root.left); // serialize left subtree
  const rightSerialized = serialize(root.right); // serialize right subtree
  return root.val + ',' + leftSerialized + ',' + rightSerialized;
}

function deserialize(data) {
  const nodes = data.split(',');
  function helper() {
    const val = nodes.shift(); // get next value
    if (val === 'null') return null; // null means no node
    const node = new TreeNode(parseInt(val)); // create node
    node.left = helper(); // build left subtree
    node.right = helper(); // build right subtree
    return node;
  }
  return helper();
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2),
  new TreeNode(3, new TreeNode(4), new TreeNode(5))
);
const serialized = serialize(root);
console.log('Serialized:', serialized);
const deserializedRoot = deserialize(serialized);

function printTree(node) {
  if (!node) return 'null';
  return node.val + ' -> ' + printTree(node.left) + ' -> ' + printTree(node.right);
}
console.log('Deserialized tree preorder:', printTree(deserializedRoot));

if (root === null) return 'null';

base case: mark null nodes explicitly

const leftSerialized = serialize(root.left);

serialize left subtree recursively

const rightSerialized = serialize(root.right);

serialize right subtree recursively

const val = nodes.shift();

read next token from serialized data

if (val === 'null') return null;

return null node when token is 'null'

node.left = helper();

build left subtree recursively

node.right = helper();

build right subtree recursively

Output

Serialized: 1,2,null,null,3,4,null,null,5,null,null

Deserialized tree preorder: 1 -> 2 -> null -> null -> 3 -> 4 -> null -> null -> 5 -> null -> null

Complexity Analysis

Time: O(n) because we visit each node once during serialization and once during deserialization

Space: O(n) for the recursion stack and the serialized string storing all nodes

vs Alternative: Compared to storing tree as nested objects or arrays, this method is compact and easy to transmit as a string

Edge Cases

Empty tree (root is null)

Serialize returns 'null' and deserialize returns null tree

DSA Javascript

if (root === null) return 'null';

Tree with only one node

Serialize returns node value with null children, deserialize rebuilds single node

DSA Javascript

if (val === 'null') return null;

Tree with only left or only right children

Nulls correctly mark missing children so tree shape is preserved

DSA Javascript

if (val === 'null') return null;

When to Use This Pattern

When you need to save or send a tree structure and later rebuild it exactly, use serialize/deserialize pattern to convert between tree and string.

Common Mistakes

Mistake: Not marking null children explicitly during serialization
Fix: Add 'null' markers for missing children to preserve tree shape

Mistake: Using split without careful order in deserialization causing wrong tree
Fix: Use a queue or shift tokens in order to rebuild tree correctly

Summary

Converts a binary tree to a string and back to the same tree.

Use when you want to save or transfer a tree structure exactly.

Mark null children explicitly to keep the tree shape during conversion.

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