/*

Using BFS (queue) approach to solve this question

- for encode:
    for each non-null node, we put the value on the result str
    for each null node, we put "n " on the result str

    so the result string will looks like: "10 5 80 n n 70 90 n n 85 100"


- for decode:
    we use a queue to store the current level non-null node
    we iterate every char in the string data
        poll a node from queue as parent node
        if parent.left is not null, we assign it to parent left, else assign null to parent left
        if parent.right is not null, we assign it to parent right, else assign null to parent right


 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        if (root==null) {
            return "";
        }

        Queue<TreeNode> q = new LinkedList<TreeNode>();
        StringBuilder sb = new StringBuilder();
        q.add(root);

        while (!q.isEmpty()) {
            TreeNode curNode=q.poll();
            if (curNode!=null){
                sb.append(curNode.val + " ");
            } else {
                // the node is null, after add the "n " to string, we must stop here!!!
                sb.append("n ");
                continue;
            }

            q.add(curNode.left);
            q.add(curNode.right);
        }

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if (data.isEmpty()) {
            return null;
        }

        Queue<TreeNode> q = new LinkedList<TreeNode>();
        String[] s = data.split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        q.add(root);

        for (int i=1; i<s.length; i++){
            TreeNode parent = q.poll();

            if (!s[i].equals("n")) {
                TreeNode leftNode = new TreeNode(Integer.parseInt(s[i]));
                parent.left = leftNode;
                q.add(leftNode);
            } else {
                parent.left = null;
            }

            if (!s[++i].equals("n")) {
                TreeNode rightNode = new TreeNode(Integer.parseInt(s[i]));
                parent.right = rightNode;
                q.add(rightNode);
            } else {
                parent.right = null;
            }

        }

        return root;

    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));