Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work.

SerializeTree.java

//     1
//    / \
//   2   3
//      / \
//     4   5
// "1 2 3 * * 4 5 * * * *"

public String serialize(TreeNode root) {
    if(root == null)
        return "";

    StringBuilder sb = new StringBuilder();
    Deque<TreeNode> queue = new LinkedList<>();

    queue.add(root);

    while(queue.size() > 0) {
        TreeNode curr = queue.poll();

        if(curr != null) {
            sb.append(curr.val + " ");
            queue.add(curr.left);
            queue.add(curr.right);
        }
        else sb.append("* ");
    }

    return sb.toString().trim();
}

public TreeNode deserialize(String data) {
    if(data == null || data.length() == 0)
        return null;

    TreeNode root = new TreeNode(Integer.parseInt(values[0]));
    Deque<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    String[] values = data.split(" ");        
    for(int i = 1; i < values.length; i++) { // Get parent from queue and children from values[]
        TreeNode parent = queue.poll();

        if(!values[i].equals("*")) {
            parent.left = new TreeNode(Integer.parseInt(values[i]));
            queue.add(parent.left);
        }

        i++;

        if(!values[i].equals("*")) {
            parent.right = new TreeNode(Integer.parseInt(values[i]));
            queue.add(parent.right);
        }     
    }

    return root;
}