# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Codec:
def serialize(self, root):
vals = []
def preorder(node):
if node:
vals.append(str(node.val))
preorder(node.left)
preorder(node.right)
preorder(root)
return ' '.join(vals)
def deserialize(self, data):
if not data:
return None
vals = list(map(int, data.split()))
def build(min_val, max_val):
if vals and min_val < vals[0] < max_val:
val = vals.pop(0)
node = TreeNode(val)
node.left = build(min_val, val)
node.right = build(val, max_val)
return node
return None
return build(float('-inf'), float('inf'))
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Codec {
public:
void preorder(TreeNode* root, string &s) {
if (!root) return;
s += to_string(root->val) + " ";
preorder(root->left, s);
preorder(root->right, s);
}
string serialize(TreeNode* root) {
string s;
preorder(root, s);
return s;
}
TreeNode* build(queue<int> &q, int minVal, int maxVal) {
if (q.empty()) return nullptr;
int val = q.front();
if (val <= minVal || val >= maxVal) return nullptr;
q.pop();
TreeNode* node = new TreeNode(val);
node->left = build(q, minVal, val);
node->right = build(q, val, maxVal);
return node;
}
TreeNode* deserialize(string data) {
if (data.empty()) return nullptr;
stringstream ss(data);
int x;
queue<int> q;
while (ss >> x) q.push(x);
return build(q, INT_MIN, INT_MAX);
}
};
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Codec {
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorder(root, sb);
return sb.toString().trim();
}
private void preorder(TreeNode node, StringBuilder sb) {
if (node == null) return;
sb.append(node.val).append(" ");
preorder(node.left, sb);
preorder(node.right, sb);
}
private int idx;
public TreeNode deserialize(String data) {
if (data.isEmpty()) return null;
String[] vals = data.split("\\s+");
idx = 0;
return build(vals, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private TreeNode build(String[] vals, int min, int max) {
if (idx == vals.length) return null;
int val = Integer.parseInt(vals[idx]);
if (val <= min || val >= max) return null;
idx++;
TreeNode node = new TreeNode(val);
node.left = build(vals, min, val);
node.right = build(vals, val, max);
return node;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var Codec = function() {};
Codec.prototype.serialize = function(root) {
let vals = [];
function preorder(node) {
if (!node) return;
vals.push(node.val);
preorder(node.left);
preorder(node.right);
}
preorder(root);
return vals.join(' ');
};
Codec.prototype.deserialize = function(data) {
if (!data) return null;
let vals = data.split(' ').map(Number);
function build(min, max) {
if (!vals.length) return null;
if (vals[0] <= min || vals[0] >= max) return null;
let val = vals.shift();
let node = new TreeNode(val);
node.left = build(min, val);
node.right = build(val, max);
return node;
}
return build(-Infinity, Infinity);
};
The task is to design an algorithm to serialize and deserialize a Binary Search Tree (BST). Serialization means converting the tree into a string so that it can be saved to a file or transferred over a network. Deserialization means reconstructing the tree from that string.
Specifically, you are given the root node of a BST. You need to implement two functions:
serialize(root): Takes the root node and returns a string representation of the tree.deserialize(data): Takes the encoded string and reconstructs the exact same BST.To serialize and deserialize a BST, the key insight is to leverage the properties of a BST: for any node, all values in the left subtree are less than the node, and all values in the right subtree are greater.
At first, it might seem natural to use a generic approach for binary trees, such as level-order traversal (BFS) or including null markers for missing children. However, these approaches add unnecessary complexity and extra markers, making the string longer.
Since the input is a BST, we can use a preorder traversal (root, left, right) to serialize the tree. Preorder uniquely defines the BST structure. For deserialization, we can reconstruct the tree efficiently by ensuring that at each step, the node values respect the BST property (using min and max bounds).
This approach is much more efficient and compact than brute-force methods, as we avoid storing nulls and only store the values in traversal order.
The solution makes use of the BST property to serialize and deserialize efficiently:
min and max bounds for valid BST node values.This approach ensures that the tree is reconstructed exactly as it was, and the serialization is compact and efficient.
Let's consider a sample BST:
5
/ \
3 7
/ \ \
2 4 8
"5 3 2 4 7 8"The optimized approach is both faster and more space-efficient compared to generic methods.
By leveraging the properties of a BST, we can serialize the tree using preorder traversal and reconstruct it using value bounds during deserialization. This method is elegant because it avoids unnecessary markers, is compact, and runs efficiently in linear time. The key insight is that preorder traversal uniquely determines the BST, allowing us to reconstruct the tree with only the node values and their order.