medium Serialize and Deserialize BST

Problem Statement

serialization means converting a data structure or object into a sequence of bits that can be stored or sent over a network. Deserialization is the reverse process, which takes this sequence and recreates the original object or data structure.

Design an algorithm to serialize and deserialize a binary search tree (BST).

The serialization should convert the BST into a string, and deserialization should reconstruct the original BST from this string. There is no restriction on how your serialization/deserialization algorithm should work.

Examples

Example 1:

• Input: root = [4, 2, 6, 1, 3, null, 7]

• Expected Output: [4, 2, 6, 1, 3, null, 7]
• Justification: The output is the same as the input.

Example 2:

• Input: root = [8, 5, 10, 2, null, null, 12]

• Expected Output: [8, 5, 10, 2, null, null, 12]
• Justification: The output is the same as the input.

Example 3:

• Input: root = [15, 10, null, 5, 12, null, null, null, 13]

• Expected Output: [15, 10, null, 5, 12, null, null, null, 13]
• Justification: The output is the same as the input.

Constraints:

• The number of nodes in the tree is in the range [0, 10⁴].
• 0 <= Node.val <= 10⁴
• The input tree is guaranteed to be a binary search tree.

Solution

To solve this problem, we will use a pre-order traversal approach to serialize the binary search tree (BST). Pre-order traversal is chosen because it processes the current node before its children, which allows the serialized string to capture the hierarchy of the BST effectively. During serialization, we will append each node's value to a string and use a special symbol like "#" to denote null nodes. This approach ensures that every position of a node or a null is represented in the serialized format, making it easier to recreate the tree during deserialization.

For deserialization, we will read the serialized string and use a queue to maintain the order of elements. Starting from the root, we will construct the tree recursively by assigning left and right children based on the serialized string. This approach is effective as it allows us to restore the original tree structure while maintaining a compact serialized format.

Step-by-Step Algorithm

Serialization Process:

1. Initialize a StringBuilder:

   • Create a StringBuilder object to store the serialized result. This will efficiently handle string concatenations.

2. Perform Pre-order Traversal:

   • Call a helper function serializeHelper with the root node and the StringBuilder as arguments.

3. Helper Function (serializeHelper):

   • Check if the Current Node is Null:
     • If the current node is null, append "#," to the StringBuilder. This symbol # represents a null or missing child.
     • Return immediately since there are no further nodes to traverse.
   • Process the Current Node:
     • Append the value of the current node followed by a comma "," to the StringBuilder.
   • Recur for the Left Subtree and Right Subtree:
     • Call serializeHelper recursively with the left child of the current node.
     • Call serializeHelper recursively with the right child of the current node.

4. Return the Serialized String:

   • Convert the StringBuilder to a string using toString() method.
   • This string represents the serialized form of the BST.

Deserialization Process:

1. Split the Serialized String:

   • Split the serialized string by commas "," to get an array of node values.
   • Convert this array into a Queue to maintain the order of nodes to be processed.

2. Reconstruct the Tree:

   • Call a helper function deserializeHelper with the queue of node values.

3. Helper Function (deserializeHelper):

   • Get the Next Node Value:
     • Retrieve the next node value from the queue using poll().
   • Check for Null Node:
     • If the retrieved value is "#", return null because this represents a null child.
   • Create a New TreeNode:
     • Convert the node value to an integer and create a new TreeNode.
   • Recur for the Left Subtree:
     • Call deserializeHelper recursively to construct the left child.
     • Assign the result to the left child of the current node.
   • Recur for the Right Subtree:
     • Call deserializeHelper recursively to construct the right child.
     • Assign the result to the right child of the current node.
   • Return the Reconstructed Node:
     • Return the current node after both left and right children are constructed.

4. Return the Root of the Reconstructed Tree:

   • The root returned by deserializeHelper represents the reconstructed tree.

Algorithm Walkthrough

Input: root = [4, 2, 6, 1, 3, null, 7]

Serialization Walkthrough:

1. Start with Root Node:

   • Initialize StringBuilder sb = "".
   • Call serializeHelper(root = 4, sb).

2. Processing Node 4:

   • Append "4," to sb → sb = "4,".
   • Recur for left subtree: Call serializeHelper(root.left = 2, sb).

3. Processing Node 2:

   • Append "2," to sb → sb = "4,2,".
   • Recur for left subtree: Call serializeHelper(root.left = 1, sb).

4. Processing Node 1:

   • Append "1," to sb → sb = "4,2,1,".
   • Recur for left child: Node is null, append "#," → sb = "4,2,1,#,".
   • Recur for right child: Node is null, append "#," → sb = "4,2,1,#,#,".

5. Back to Node 2:

   • Recur for right subtree: Call serializeHelper(root.right = 3, sb).

6. Processing Node 3:

   • Append "3," to sb → sb = "4,2,1,#,#,3,".
   • Recur for left child: Node is null, append "#," → sb = "4,2,1,#,#,3,#,".
   • Recur for right child: Node is null, append "#," → sb = "4,2,1,#,#,3,#,#,".

7. Back to Node 4:

   • Recur for right subtree: Call serializeHelper(root.right = 6, sb).

8. Processing Node 6:

   • Append "6," to sb → sb = "4,2,1,#,#,3,#,#,6,".
   • Recur for left child: Node is null, append "#," → sb = "4,2,1,#,#,3,#,#,6,#,".
   • Recur for right subtree: Call serializeHelper(root.right = 7, sb).

9. Processing Node 7:

   • Append "7," to sb → sb = "4,2,1,#,#,3,#,#,6,#,7,".
   • Recur for left child: Node is null, append "#," → sb = "4,2,1,#,#,3,#,#,6,#,7,#,".
   • Recur for right child: Node is null, append "#," → sb = "4,2,1,#,#,3,#,#,6,#,7,#,#,".

10. Final Serialized String:

• Serialized = "4,2,1,#,#,3,#,#,6,#,7,#,#".

Deserialization Walkthrough:

1. Initialize Queue from Serialized String:

   • Split serialized string "4,2,1,#,#,3,#,#,6,#,7,#,#" into a queue:
     Queue = ["4", "2", "1", "#", "#", "3", "#", "#", "6", "#", "7", "#", "#"].

2. Start Deserialization:

   • Call deserializeHelper(Queue).

3. Processing Node 4:

   • Dequeue "4" → Create TreeNode(4).
   • Recur for left child: Call deserializeHelper(Queue).

4. Processing Node 2:

   • Dequeue "2" → Create TreeNode(2).
   • Recur for left child: Call deserializeHelper(Queue).

5. Processing Node 1:

   • Dequeue "1" → Create TreeNode(1).
   • Recur for left child: Dequeue "#", return null.
   • Recur for right child: Dequeue "#", return null.
   • Return to Node 2.

6. Back to Node 2:

   • Recur for right child: Call deserializeHelper(Queue).

7. Processing Node 3:

   • Dequeue "3" → Create TreeNode(3).
   • Recur for left child: Dequeue "#", return null.
   • Recur for right child: Dequeue "#", return null.
   • Return to Node 4.

8. Back to Node 4:

   • Recur for right child: Call deserializeHelper(Queue).

9. Processing Node 6:

   • Dequeue "6" → Create TreeNode(6).
   • Recur for left child: Dequeue "#", return null.
   • Recur for right child: Call deserializeHelper(Queue).

10. Processing Node 7:

    • Dequeue "7" → Create TreeNode(7).
    • Recur for left child: Dequeue "#", return null.
    • Recur for right child: Dequeue "#", return null.

11. Final Tree Structure Reconstructed:

    • The tree is reconstructed as [4, 2, 6, 1, 3, null, 7].

Code

import java.util.*;

// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) {
//         val = x;
//     }
// }

class Solution {

  // Function to serialize the BST
  public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder(); // StringBuilder to store the serialized result
    serializeHelper(root, sb);
    return sb.toString();
  }

  // Helper function for pre-order traversal
  private void serializeHelper(TreeNode root, StringBuilder sb) {
    if (root == null) {
      sb.append("#,"); // Use "#" to denote null nodes
      return;
    }
    sb.append(root.val).append(","); // Append the node value followed by a comma
    serializeHelper(root.left, sb); // Recur for the left subtree
    serializeHelper(root.right, sb); // Recur for the right subtree
  }

  // Function to deserialize the serialized string back to BST
  public TreeNode deserialize(String data) {
    Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(","))); // Split data into a queue
    return deserializeHelper(nodes);
  }

  // Helper function to rebuild the tree
  private TreeNode deserializeHelper(Queue<String> nodes) {
    String value = nodes.poll(); // Retrieve the next node value
    if (value.equals("#")) return null;
    TreeNode root = new TreeNode(Integer.parseInt(value));
    root.left = deserializeHelper(nodes); // Recur for the left subtree
    root.right = deserializeHelper(nodes); // Recur for the right subtree
    return root;
  }

  // Function to convert BST to array format using level-order traversal
  public List<String> treeToArray(TreeNode root) {
    List<String> result = new ArrayList<>(); // List to store the tree in array format
    if (root == null) return result; // Return empty if root is null

    Queue<TreeNode> queue = new LinkedList<>(); // Queue for level-order traversal
    queue.offer(root); // Start with the root

    while (!queue.isEmpty()) {
      TreeNode node = queue.poll(); // Get the current node from the queue
      if (node == null) {
        result.add("null"); // Add "null" for missing nodes
        continue;
      }
      result.add(String.valueOf(node.val)); // Add the current node's value
      queue.offer(node.left); // Add left child to the queue
      queue.offer(node.right); // Add right child to the queue
    }

    // Remove trailing "null" values
    while (result.get(result.size() - 1).equals("null")) {
      result.remove(result.size() - 1);
    }

    return result; // Return the array representation of the tree
  }

  // Main method to test the solution
  public static void main(String[] args) {
    Solution sol = new Solution();
    TreeNode root = new TreeNode(4); // Creating example tree
    root.left = new TreeNode(2);
    root.right = new TreeNode(6);
    root.left.left = new TreeNode(1);
    root.left.right = new TreeNode(3);
    root.right.right = new TreeNode(7);

    String serialized = sol.serialize(root); // Serialize the BST
    System.out.println("Serialized: " + serialized);

    TreeNode deserialized = sol.deserialize(serialized); // Deserialize the string

    List<String> arrayRepresentation = sol.treeToArray(deserialized); // Convert tree to array format
    System.out.println("Deserialized as Array: " + arrayRepresentation); // Print the array representation
  }
}

Complexity Analysis

TIme Complexity

1. Serialization Complexity:
   • Time Complexity: The serialize method uses a pre-order traversal to visit each node exactly once, resulting in a time complexity of , where n is the number of nodes in the BST.
2. Deserialization Complexity:
   • Time Complexity: The deserialize method rebuilds the tree by processing each node value from the serialized string. This takes time since each node is processed once.

Space Complexity

1. Serialization Complexity:
   • Space Complexity: The space complexity is due to the queue used to store the node values during reconstruction.
2. Deserialization Complexity:
   • Space Complexity: The space complexity is also because we store the serialized result in a string and also use a StringBuilder to construct it.