Serialization is to store a tree in an array so that it can be later restored and deserialization is reading tree back from the array. Complete the functions
- serialize() : stores the tree into an array a and returns the array.
- deSerialize() : deserializes the array to the tree and returns the root of the tree.
Note: Multiple nodes can have the same data and the node values are always positive integers. Your code will be correct if the tree returned by deSerialize(serialize(input_tree)) is same as the input tree. Driver code will print the in-order traversal of the tree returned by deSerialize(serialize(input_tree)).
Examples :
Input: root = [1, 2, 3]Output: [2, 1, 3]
Input: root = [10, 20, 30, 40, 60, N, N]Output: [40, 20, 60, 10, 30]
Constraints:
1 <= Number of nodes <= 104
1 <= Data of a node <= 109
Approach 01:
-
C++
-
Python
#include <queue>
#include <vector>
class Solution {
public:
// Helper function for inorder traversal during serialization
void inorderTraversal(Node* root, vector<int>& serializedTree) {
if (root == nullptr) return;
inorderTraversal(root->left, serializedTree);
serializedTree.push_back(root->data);
inorderTraversal(root->right, serializedTree);
}
// Serialize the binary tree into a vector using inorder traversal
vector<int> serialize(Node *root) {
vector<int> serializedTree;
inorderTraversal(root, serializedTree);
return serializedTree;
}
// Helper function to recursively construct the tree during deserialization
void constructTree(vector<int>& serializedTree, int index, Node* root, Node*& resultTree) {
if (index >= serializedTree.size()) return;
Node* currentNode = new Node(serializedTree[index]);
currentNode->left = root;
if (index + 1 < serializedTree.size()) {
Node* rightNode = new Node(serializedTree[index + 1]);
currentNode->right = rightNode;
}
resultTree = currentNode;
constructTree(serializedTree, index + 2, currentNode, resultTree);
}
// Deserialize the vector into a binary tree
Node* deSerialize(vector<int>& serializedTree) {
Node* root = new Node(serializedTree[0]);
if (serializedTree.size() == 1) {
return root;
}
Node* resultTree = nullptr;
constructTree(serializedTree, 1, root, resultTree);
return resultTree;
}
};
class Solution:
def inorderTraversal(self, root, serializedTree):
if not root:
return
self.inorderTraversal(root.left, serializedTree)
serializedTree.append(root.data)
self.inorderTraversal(root.right, serializedTree)
def serialize(self, root):
serializedTree = []
self.inorderTraversal(root, serializedTree)
return serializedTree
def constructTree(self, serializedTree, index, root, resultTree):
if index >= len(serializedTree):
return
currentNode = Node(serializedTree[index])
currentNode.left = root
if index + 1 < len(serializedTree):
rightNode = Node(serializedTree[index + 1])
currentNode.right = rightNode
resultTree[0] = currentNode
self.constructTree(serializedTree, index + 2, currentNode, resultTree)
def deSerialize(self, serializedTree):
root = Node(serializedTree[0])
if len(serializedTree) == 1:
return root
resultTree = [None]
self.constructTree(serializedTree, 1, root, resultTree)
return resultTree[0]
Time Complexity:
- Serialization:
The
serializefunction performs an inorder traversal of the binary tree, which takes \( O(n) \) time. - Deserialization:
The
deSerializefunction reconstructs the tree using a recursive approach, which also takes \( O(n) \) time. - Total Time Complexity:
Since both serialization and deserialization run in \( O(n) \) time, the overall time complexity is \( O(n) \).
Space Complexity:
- Serialization Storage:
The serialized tree is stored in a vector of size \( O(n) \).
- Recursive Stack:
The recursion depth in the worst case (a skewed tree) is \( O(n) \).
- Total Space Complexity:
The total space complexity is \( O(n) \) due to both the vector storage and recursion stack.