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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Codec:
8
9 def serialize(self, root):
10 def preorder(node):
11 return [str(node.val)] + preorder(node.left) + preorder(node.right) if node else []
12
13 return ' '.join(preorder(root))
14
15 def deserialize(self, data):
16 if not data:
17 return None
18
19 def buildTree(bounds):
20 if not data or not(bounds[0] < int(data[-1]) < bounds[1]):
21 return None
22
23 val = int(data.pop())
24 node = TreeNode(val)
25 node.right = buildTree((val, bounds[1]))
26 node.left = buildTree((bounds[0], val))
27 return node
28
29 data = data.split()[::-1]
30 return buildTree((-float('inf'), float('inf')))The serialize function performs a pre-order traversal to create a space-separated string of node values. The deserialize function reads from this string (reversed) and reconstructs the tree by checking the constraints for valid BST nodes, creating a tree using bounds for node values as it progresses.
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 val
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.