JAVA | Serialize & De- BST | 99 % | Explained | O(N) both sides

134

A BST is well structured.. so a preorder traversal ie. Root - Left-Right order will ALWAYS be same if serialized and deserialized.
Hence, do a preorder and add to string (use a stringbuilder to save string pool space).
And create a BST out of it like you would normally do.

WHILE creating the BST, we do it by taking high and low parameters, As we know BST follow rule left<root<right. Hence It helps us to create BST in a single go.

public class Codec {

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

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null || data.length()==0)
            return null;

        this.data_arr = data.split("/");

        return BSTBuilder(null,new int[]{0},Integer.MAX_VALUE, Integer.MIN_VALUE);
    }
    
    private TreeNode BSTBuilder(TreeNode root, int[] idx, int high, int low){
        if(idx[0]>=this.data_arr.length)
            return root;
        int val = Integer.valueOf(this.data_arr[idx[0]]);
        
        if(val>high || val<low){
            idx[0]--;
            return null;
        }
        
        root = new TreeNode(val);
        
        idx[0]++;
        root.left = BSTBuilder(root.left,idx,val,low);
        
        idx[0]++;
        root.right = BSTBuilder(root.right,idx,high,val);
        return root;
    }
}

Comments (0)