Serialize and Deserialize BST

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.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Approach

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class SerializeDeserializeBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        String data = serialize(root);
        root = deserialize(data);
        printTree(root);
    }

    static int index = 0;

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

        // post order traversal: left, right, root
        StringBuilder sb = new StringBuilder();

        // left
        String left = serialize(root.left);
        if (left.length() > 0) {
            sb.append(left).append(",");
        }

        // right
        String right = serialize(root.right);
        if (right.length() > 0) {
            sb.append(right).append(",");
        }

        // root
        sb.append(root.val).append(",");

        String result = sb.substring(0, sb.length() - 1).toString();
        return result;
    }

    // Decodes your encoded data to tree.
    static public TreeNode deserialize(String data) {
        if (data.length() <= 0) {
            return null;
        }
        String[] array = data.split(",");
        index = array.length - 1;
        return helper(array, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    static public TreeNode helper(String[] array, int lower, int upper) {
        if (index < 0) {
            return null;
        }
        int num = Integer.valueOf(array[index]);
        if (num < lower || num > upper) {
            return null;
        }
        index--;
        TreeNode root = new TreeNode(num);
        root.right = helper(array, num, upper);
        root.left = helper(array, lower, num);
        return root;
    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        while (j > 0 && vec.get(j) == "null")
            j--;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }

}

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;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

//function to encode tree into
//the string
string serialize(TreeNode *root)
{
    if (root == NULL)
        return "";
    string ans = to_string(root->data) + ",";

    //call for left subtree
    ans += serialize(root->left);

    //call for right subtree
    ans += serialize(root->right);
    return ans;
}

//function to find the nth
int findnth(string &data, int &pos)
{
    pos = data.find(",");
    int val1 = stoi(data.substr(0, pos));
    return val1;
}
TreeNode *deserialize(string &data, int max1)
{
    int pos = 0;
    if (data.size() == 0)
        return NULL;
    int val1 = findnth(data, pos);
    if (val1 > max1)
        return NULL;

    //store the substring from pos+1 to end
    data = data.substr(pos + 1);

    //make the root
    TreeNode *root = new TreeNode(val1);

    //call for left subtree
    root->left = deserialize(data, val1);

    //call for right subtree
    root->right = deserialize(data, max1);
    return root;
}
// function to decodes the encoded data to tree.
TreeNode *deserialize(string data)
{
    if (data.size() == 0)
        return NULL;
    return deserialize(data, INT_MAX);
}

//function to print the tree
void printTree(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    vector<string> vec;
    while (!q.empty())
    {
        root = q.front();
        q.pop();
        if (root == NULL)
            vec.push_back("null");
        else
            vec.push_back(to_string(root->data));
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
    }
    int j = vec.size() - 1;
    while (j > 0 && vec[j] == "null")
        j--;
    vec.resize(j);
    cout << "[";
    for (int i = 0; i < j; i++)
        cout << vec[i] << ",";
    cout << vec[j];
    cout << "]";
}
int main()
{
    TreeNode *root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    string data = serialize(root);
    root = deserialize(data);
    printTree(root);
    return 0;
}