import java.util.LinkedList;

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

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) { // Level-order traversal
        StringBuilder sb = new StringBuilder();
		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
		list.add(root);
		TreeNode curr;
		while (!list.isEmpty()) {
			curr = list.poll();
			if (curr == null) {
				sb.append("null,");
				continue;
			}
			sb.append(curr.val);
			sb.append(',');
			list.add(curr.left);
			list.add(curr.right);
		}
		sb.deleteCharAt(sb.length()-1); // Remove the last ','
		return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
		String[] strs = data.split(",");
		if (strs[0].equals("null")) return null; // Root is null
		TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
		list.add(root);
		int idx = 1;
		while (!list.isEmpty()) {
			TreeNode curr = list.poll();
			if (idx < strs.length) {
				if (!strs[idx].equals("null")) {
					curr.left = new TreeNode(Integer.parseInt(strs[idx]));
					list.add(curr.left);
				}
				idx++;
			}
			if (idx < strs.length) {
				if (!strs[idx].equals("null")) {
					curr.right = new TreeNode(Integer.parseInt(strs[idx]));
					list.add(curr.right);
				}
				idx++;
			}
		}
        return root;
    }
}

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