LeetCode Solution 297 - Serialize and Deserialize Binary Tree

Problem Statement

The problem "Serialize and Deserialize Binary Tree" (LeetCode 297) requires us to design an algorithm to convert a binary tree into a string (serialization) and then reconstruct it back into the original tree (deserialization).

Constraints:

• The input tree may have NULL values.
• The solution should efficiently handle large trees.
• It should preserve the original tree structure.

---

Optimal Approach: BFS (Level Order Traversal) using Queue

The best approach to solve this problem is using Breadth-First Search (BFS) with a queue. This method ensures that nodes are serialized and deserialized in the correct order, maintaining the structure of the tree.

Steps:

1. Serialization:

   • Use level-order traversal (BFS) to process nodes.
   • Convert each node's value to a string.
   • Use a delimiter (e.g., ,) to separate values.
   • Represent NULL nodes as "#".

2. Deserialization:

   • Split the serialized string using the delimiter.
   • Reconstruct the tree using a queue.
   • Process nodes in the correct order and attach left/right children accordingly.

---

C++ Implementation (LeetCode Compatible)

#include <iostream>
#include <sstream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        
        stringstream ss;
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            
            if (node) {
                ss << node->val << ",";
                q.push(node->left);
                q.push(node->right);
            } else {
                ss << "#,";
            }
        }
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        
        stringstream ss(data);
        string item;
        getline(ss, item, ',');
        TreeNode* root = new TreeNode(stoi(item));
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            
            if (getline(ss, item, ',') && item != "#") {
                node->left = new TreeNode(stoi(item));
                q.push(node->left);
            }
            
            if (getline(ss, item, ',') && item != "#") {
                node->right = new TreeNode(stoi(item));
                q.push(node->right);
            }
        }
        return root;
    }
};

---

Step-by-Step Explanation

Serialization

• We perform level-order traversal (BFS) using a queue.
• Store the node values separated by ,.
• Represent NULL nodes as "#".

Deserialization

• Split the string into tokens using ,.
• Reconstruct the tree by processing elements sequentially.
• Use a queue to maintain parent-child relationships.

---

Dry Run Example

Input Tree:

        1
       / \
      2   3
         / \
        4   5

Serialized String:

"1,2,3,#,#,4,5,#,#,#,#,"

Deserialized Tree:

• Read "1", create root.
• Read "2", add as left child of 1.
• Read "3", add as right child of 1.
• "#" means no left child for 2.
• "#" means no right child for 2.
• Read "4", add as left child of 3.
• Read "5", add as right child of 3.
• "#" for null children of 4 and 5.

---

Alternative Approaches & Their Limitations

Approach	Time Complexity	Space Complexity	Why Not Optimal?
DFS (Preorder)	O(N)	O(N)	Can fail for unbalanced trees
DFS (Postorder)	O(N)	O(N)	Harder to reconstruct
DFS (Inorder)	O(N)	O(N)	Cannot reconstruct tree uniquely

---

Best Solution & Why It’s Best

• BFS Level-Order Traversal is the best choice because:
  • It preserves tree structure efficiently.
  • It works well for balanced and unbalanced trees.
  • It provides predictable serialization and deserialization.

Time Complexity:

• O(N) for both serialization and deserialization (visits each node once).
• O(N) space for storing nodes in a queue.

---

Complexity Analysis

Operation	Time Complexity	Space Complexity
Serialization	O(N)	O(N)
Deserialization	O(N)	O(N)

---

Conclusion

• Breadth-First Search (BFS) is the best approach for this problem.
• The queue-based approach ensures efficient tree reconstruction.
• Practice Similar Problems:
  • Binary Tree Preorder Traversal
  • Binary Tree Level Order Traversal
  • Construct Binary Tree from Preorder and Inorder Traversal

Happy Coding! 🚀