449. Serialize and Deserialize BST

Description

Serialization is 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 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.

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 binary search tree.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: root = [2, 1, 3]

Output: [2, 1, 3]

Example 2

Input: root = []

Output: []

Solutions

TreeNode

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        StringBuilder sb = new StringBuilder();
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node != null) {
                sb.append(node.val).append(",");
                stack.push(node.right);
                stack.push(node.left);
            } else {
                sb.append("#,");
            }
        }
        return sb.substring(0, sb.length()-1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        
        return helper(data.split(","), new int[]{0});
    }
    
    private TreeNode helper(String[] values, int[] index) {
        if("#".equals(values[index[0]])) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(values[index[0]]));
        
        index[0] += 1;
        node.left = helper(values, index);
        
        index[0] += 1;
        node.right = helper(values, index);
        
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;

        StringBuilder sb = new StringBuilder();
        serialize(root, sb);

        return sb.substring(0, sb.length()-1);
    }
    
    private void serialize(TreeNode node, StringBuilder sb) {
        if(node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(",");
        serialize(node.left, sb);
        serialize(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        
        return helper(data.split(","), new int[]{0});
    }
    
    private TreeNode helper(String[] values, int[] index) {
        if("#".equals(values[index[0]])) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(values[index[0]]));
        
        index[0] += 1;
        node.left = helper(values, index);
        
        index[0] += 1;
        node.right = helper(values, index);
        
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;

Follow up