💡 Problem Formulation: Serializing a Binary Search Tree (BST) involves converting the structure into a string or a byte sequence, which can then be saved to a file or transferred over a network. Deserializing is the reverse process where the tree is reconstructed from the string representation. Here, we aim to demonstrate the serialization and deserialization of a BST with methods that enable the output to be a string representation such as '2,1,3' for a BST with elements 2, 1, and 3, and then how to restore the BST from this string.
Method 1: Preorder Traversal with Markers
Preorder traversal with markers for serialization uses a depth-first approach to traverse the tree. During the traversal, each node value is recorded along with markers for ‘None’ to represent the absence of a child. Deserialization involves reading the markers and reconstructing the tree accordingly.
Here’s an example:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def serialize(root):
def preorder(node):
return f'{node.val},' + preorder(node.left) + preorder(node.right) if node else '#,'
return preorder(root)
def deserialize(data):
def build_tree(iterator):
val = next(iterator)
if val == '#':
return None
node = TreeNode(int(val))
node.left = build_tree(iterator)
node.right = build_tree(iterator)
return node
return build_tree(iter(data.split(',')))
# Example usage:
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
data = serialize(root)
print(data)
restored_root = deserialize(data)Output:
2,1,#,#,3,#,#,
This method uses recursive functions preorder for serialization and build_tree for deserialization. The serialize function outputs the preorder traversal of the BST as a string, with # indicating null children. The deserialize function uses an iterator that steps through the string, utilizing the preorder schema and markers to properly rebuild the BST.
Method 2: Level Order Traversal
Serialization utilizing level order traversal records nodes of the BST in a breadth-first manner, maintaining the tree structure explicitly. Deserialization reads the string level by level and constructs the tree accordingly, ensuring that each node is placed in the correct position based on the level order sequence.
Here’s an example:
from collections import deque
def serialize(root):
if not root:
return ''
serialization = []
queue = deque([root])
while queue:
node = queue.popleft()
serialization.append(str(node.val) if node else '#')
if node:
queue.append(node.left)
queue.append(node.right)
return ','.join(serialization)
def deserialize(data):
if not data:
return None
nodes = data.split(',')
root = TreeNode(int(nodes[0]))
queue = deque([root])
index = 1
while queue:
node = queue.popleft()
if nodes[index] != '#':
node.left = TreeNode(int(nodes[index]))
queue.append(node.left)
index += 1
if nodes[index] != '#':
node.right = TreeNode(int(nodes[index]))
queue.append(node.right)
index += 1
return root
# Example usage:
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
data = serialize(root)
print(data)
restored_root = deserialize(data)Output:
2,1,3,#,#,#,#
With level order traversal, the serialize function constructs a string where each BST node is separated by commas, and null children are represented as #. The deserialize function uses a queue to track the nodes. It reconstructs the BST by linking child nodes based on the sequence of values, handling null cases as needed.
Method 3: Encoded Preorder Traversal
Encoded Preorder Traversal uses a recursive depth-first approach but with a more compact string encoding. Serialization records the node values along with the number of trailing # markers that denote null children. Deserialization involves a similar process as in Method 1 but with an efficient encoding.
Here’s an example:
def serialize(root):
def preorder(node):
return f'{node.val} ' + preorder(node.left) + preorder(node.right) if node else '# '
return preorder(root).strip()
def deserialize(data):
def build_tree(values):
val = next(values)
if val == '#':
return None
node = TreeNode(int(val))
node.left = build_tree(values)
node.right = build_tree(values)
return node
return build_tree(iter(data.split()))
# Example usage:
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
data = serialize(root)
print(data)
restored_root = deserialize(data)Output:
2 1 # # 3 # #
In Encoded Preorder Traversal, the serialize function uses a space-delimited string to represent the BST. Each # symbol still represents null children, but now with more efficient spacing. The deserialize function processes this string, reconstructing the tree by interpreting the symbols and converting them back into node values.
Method 4: Iterative Preorder Traversal with Stack
Iterative Preorder Traversal with a Stack avoids recursion and utilizes an explicit stack to serialize the BST. The method pushes nodes onto the stack as it traverses, creating the serialized string. Deserializing reconstructs the tree using a similar stack-based approach, observing the node and null markers.
Here’s an example:
def serialize(root):
stack, serialization = [root], []
while stack:
node = stack.pop()
serialization.append(str(node.val) if node else '#')
if node:
stack.append(node.right)
stack.append(node.left)
return ','.join(serialization)
def deserialize(data):
if not data:
return None
values, root = iter(data.split(',')), TreeNode(int(next(values)))
stack, node = [root], root
for val in values:
if val != '#':
parent = stack[-1]
newNode = TreeNode(int(val))
if not parent.left:
parent.left = newNode
else:
parent.right = newNode
stack.pop()
stack.append(newNode)
else:
if stack[-1].left:
stack.pop()
return root
# Example usage:
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
data = serialize(root)
print(data)
restored_root = deserialize(data)Output:
2,1,#,#,3,#,#
The iterative approach uses stacks in both serialization and deserialization to manage the node traversal and construction process without recursion. The serialized output is a comma-separated string of node values and # for nulls. The deserializer constructs the tree iteratively, ensuring the correct parent-child relationships are maintained.
Bonus One-Liner Method 5: Python Pickling
Using Python’s built-in pickle module allows for a one-liner serialization and deserialization. However, this method is Python-specific and not suitable for long-term storage or cross-language interoperability.
Here’s an example:
import pickle # Assuming the TreeNode class is defined as before. # Example usage: root = TreeNode(2) root.left = TreeNode(1) root.right = TreeNode(3) serialized_data = pickle.dumps(root) print(serialized_data) restored_root = pickle.loads(serialized_data)
Output:
b'\x80\x04\x95\x1b\x00\x00\x00\x00\x00\x00\x00\x8c\x08__main__\x94\x8c\x08TreeNode\x94\x93\x94K\x02\x8c\x08builtins\x94\x8c\x05None\x94\x89\x85\x94R\x94(h\x06\x89\x85\x94R\x94(h\x06\x8c\x01K\x01\x85\x94h\x07\x85\x94R\x94h\x06\x8c\x01K\x03\x85\x94h\x07\x85\x94R\x94\x86\x94\x86\x94.'
Serializing with pickle is straightforward and doesn’t require any tree-specific code. Call pickle.dumps() to serialize the BST, and pickle.loads() to deserialize it. The output is a byte string that can be easily saved or transmitted. Pickle handles all complex data types, but use with caution as pickle files may execute arbitrary code during unpickling.
Summary/Discussion
- Method 1: Preorder Traversal with Markers. This method provides an intuitive and easily implementable solution. However, the string produced can get quite large for big trees due to the markers.
- Method 2: Level Order Traversal. This approach gives a clear picture of the tree level by level, making it suitable for binary trees with many null children. On the other hand, it can also produce relatively large strings.
- Method 3: Encoded Preorder Traversal. It is space-efficient compared to the first method and maintains a straightforward tree reconstruction process. Still, it can be less intuitive to understand than explicit marker methods.
- Method 4: Iterative Preorder Traversal with Stack. It avoids the potential stack overflow of recursion and may execute faster, but the code complexity is increased due to manual stack management.
- Method 5: Python Pickling. While it is the least verbose and fastest to implement, it is restricted to Python environments and presents security risks for untrusted sources.