algoadvance

Leetcode 449. Serialize and Deserialize BST

Problem Statement

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Clarifying Questions

  1. What type of tree is it?
    • It is a Binary Search Tree (BST).
  2. Can the tree have duplicate values?
    • The problem does not mention duplicates, so we’ll assume no duplicates in the node values.
  3. What should the structure of the serialized data be?
    • There is no restriction on the format as long as it can be serialized and deserialized reliably.
  4. Are there any constraints on node values?
    • Assume typical integer values for the nodes in the binary search tree.

Strategy

To serialize the BST, we can use a pre-order traversal approach that allows us to capture the structure of the tree effectively. In pre-order traversal, we visit the root node first, followed by the left subtree, and then the right subtree. This traversal will help us capture the parent-child relationship directly, which is crucial for reconstructing the tree.

For deserialization, we can use the pre-order sequence, reconstructing the tree by recursively determining the bounds for the left and right subtrees.

Code Implementation

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    
    private void serializeHelper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("null,");
            return;
        }
        sb.append(root.val).append(",");
        serializeHelper(root.left, sb);
        serializeHelper(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> nodesQueue = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(nodesQueue);
    }

    private TreeNode deserializeHelper(Queue<String> nodesQueue) {
        String value = nodesQueue.poll();
        if (value.equals("null")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(value));
        node.left = deserializeHelper(nodesQueue);
        node.right = deserializeHelper(nodesQueue);
        return node;
    }

    // TreeNode class definition for the Binary Tree nodes
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        
        TreeNode() {}
        
        TreeNode(int val) {
            this.val = val;
        }
        
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

Time Complexity

This approach ensures that both serialization and deserialization are efficient and work within linear time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI