Practice/LinkedIn/Leetcode 449. Serialize and Deserialize BST

Leetcode 449. Serialize and Deserialize BST

CodingMust

Problem

Create two methods for a Codec class that can convert a Binary Search Tree into a compact string representation and restore it back to the original tree structure.

Your implementation should:

• serialize(root): Convert a BST into a string format
• deserialize(data): Reconstruct the BST from the string format

The key challenge is to leverage the BST property (left subtree values < node value < right subtree values) to create an efficient encoding that doesn't require storing null markers or explicit structural information beyond the node values themselves.

Requirements

1. Implement serialize to convert a BST to a string representation
2. Implement deserialize to reconstruct the exact original BST from the string
3. Take advantage of BST ordering properties to minimize the encoded size
4. Ensure that deserialize(serialize(tree)) produces a tree identical to the original
5. The encoding should be unambiguous and space-efficient

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 valid binary search tree
• Your solution should work for empty trees (null root)

Examples

Example 1:

` Input: root = [2,1,3] 2 /
1 3

serialize(root) = "2,1,3" deserialize("2,1,3") reconstructs the same tree `

Example 2:

` Input: root = [5] 5

serialize(root) = "5" deserialize("5") reconstructs a single-node tree `

Example 3:

Input: root = [] serialize(root) = "" deserialize("") returns null

Example 4:

` Input: root = [10,5,15,2,7,null,20] 10 /
5 15 / \
2 7 20

serialize(root) = "10,5,2,7,15,20" (preorder traversal is sufficient due to BST property) `