Grokking Tree Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Serialize and Deserialize BST
On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

TIme Complexity

Space Complexity

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]
Image
  • 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]
Image
  • 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]
Image
  • 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<sup>4</sup>].
  • 0 <= Node.val <= 10<sup>4</sup>
  • 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:

Image

  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:

Image

  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

Python3
Python3
. . . .

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 O(n), 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 O(n) time since each node is processed once.

Space Complexity

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

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

TIme Complexity

Space Complexity