449. Serialize and Deserialize BST LeetCode Solution
In this guide, you will get 449. Serialize and Deserialize BST LeetCode Solution with the best time and space complexity. The solution to Serialize and Deserialize BST problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Serialize and Deserialize BST
Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Example 1:
Input: root = [2,1,3]
Output: [2,1,3]
Example 2:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The input tree is guaranteed to be a binary search tree.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
449. Serialize and Deserialize BST LeetCode Solution in C++
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == nullptr)
return "";
string s;
serialize(root, s);
return s;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data.empty())
return nullptr;
istringstream iss(data);
queue<int> q;
for (string s; iss >> s;)
q.push(stoi(s));
return deserialize(INT_MIN, INT_MAX, q);
}
private:
void serialize(TreeNode* root, string& s) {
if (root == nullptr)
return;
s += to_string(root->val) + " ";
serialize(root->left, s);
serialize(root->right, s);
}
TreeNode* deserialize(int mn, int mx, queue<int>& q) {
if (q.empty())
return nullptr;
const int val = q.front();
if (val < mn || val > mx)
return nullptr;
q.pop();
TreeNode* root = new TreeNode(val);
root->left = deserialize(mn, val, q);
root->right = deserialize(val, mx, q);
return root;
}
}; /* code provided by PROGIEZ */
449. Serialize and Deserialize BST LeetCode Solution in Java
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null)
return "";
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty())
return null;
final String[] vals = data.split(" ");
Queue<Integer> q = new ArrayDeque<>();
for (final String val : vals)
q.offer(Integer.parseInt(val));
return deserialize(Integer.MIN_VALUE, Integer.MAX_VALUE, q);
}
private void serialize(TreeNode root, StringBuilder sb) {
if (root == null)
return;
sb.append(root.val).append(" ");
serialize(root.left, sb);
serialize(root.right, sb);
}
private TreeNode deserialize(int mn, int mx, Queue<Integer> q) {
if (q.isEmpty())
return null;
final int val = q.peek();
if (val < mn || val > mx)
return null;
q.poll();
TreeNode root = new TreeNode(val);
root.left = deserialize(mn, val, q);
root.right = deserialize(val, mx, q);
return root;
}
} // code provided by PROGIEZ
449. Serialize and Deserialize BST LeetCode Solution in Python
class Codec:
def serialize(self, root: TreeNode | None) -> str:
"""Encodes a tree to a single string."""
if not root:
return ''
chars = []
self._serialize(root, chars)
return ''.join(chars)
def deserialize(self, data: str) -> TreeNode | None:
"""Decodes your encoded data to tree."""
if not data:
return None
q = collections.deque(int(val) for val in data.split())
return self._deserialize(-math.inf, math.inf, q)
def _serialize(self, root: TreeNode | None, chars: list[str]) -> None:
if not root:
return
chars.append(str(root.val))
chars.append(' ')
self._serialize(root.left, chars)
self._serialize(root.right, chars)
def _deserialize(
self,
mn: int,
mx: int,
q: collections.deque[int]
) -> TreeNode | None:
if not q:
return None
val = q[0]
if val < mn or val > mx:
return None
q.popleft()
return TreeNode(val,
self._deserialize(mn, val, q),
self._deserialize(val, mx, q)) # code by PROGIEZ
