Sponsored
Sponsored
In this approach, we utilize pre-order traversal (Root-Left-Right) to serialize the BST. The serialized string will be a space-separated string that represents the order of visiting nodes during pre-order traversal.
During deserialization, you use the properties of the pre-order traversal and BST to reconstruct the tree. The key is to maintain the order of insertions such that it respects BST properties.
Time Complexity: O(n) for both serialization and deserialization, where n is the number of nodes.
Space Complexity: O(n) for storing the serialized data.
1#include <string>
2#include <sstream>
3#include <vector>
4#include <climits>
5#include <algorithm>
6
7struct TreeNode {
8 int val;
9 TreeNode *left;
10 TreeNode *right;
11 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12};
13
14class Codec {
15public:
16
17 // Encodes a tree to a single string.
18 std::string serialize(TreeNode* root) {
19 std::string data;
20 preorder(root, data);
21 return data;
22 }
23
24 // Decodes your encoded data to tree.
25 TreeNode* deserialize(std::string data) {
26 std::istringstream iss(data);
27 std::vector<int> nodes;
28 std::string token;
29 while (iss >> token) {
30 nodes.push_back(std::stoi(token));
31 }
32 std::reverse(nodes.begin(), nodes.end());
33 return buildTree(nodes, INT_MIN, INT_MAX);
34 }
35
36private:
37
38 void preorder(TreeNode* node, std::string& data) {
39 if (node) {
40 data += std::to_string(node->val) + " ";
41 preorder(node->left, data);
42 preorder(node->right, data);
43 }
44 }
45
46 TreeNode* buildTree(std::vector<int>& nodes, int lower, int upper) {
47 if (nodes.empty() || nodes.back() < lower || nodes.back() > upper) {
48 return nullptr;
49 }
50
51 int val = nodes.back();
52 nodes.pop_back();
53 TreeNode* node = new TreeNode(val);
54 node->right = buildTree(nodes, val, upper);
55 node->left = buildTree(nodes, lower, val);
56 return node;
57 }
58};In this C++ solution, the serialize method performs a pre-order traversal while appending node values to a string. For deserialize, the string is split and reversed into a vector of integers, and a BST is reconstructed using bounds to ensure the properties are maintained.
Level-order traversal (BFS) involves visiting each level of the tree one at a time, which can be used to serialize the tree into a compact form. For empty positions, we can indicate using a special character (e.g., '#'). This method guarantees that we record the full structure of the tree including missing nodes.
Time Complexity: O(n) for both serialization and deserialization.
Space Complexity: O(n) due to the queue usage in both processes.
1public class TreeNode {
2 int
This Java solution serialized the BST using a level-order traversal, noting nulls for missing children. During deserialization, nodes are reconstructed level by level, keeping track of parents and appending appropriate left and right children.