[Java] Solution - Level Order Traversal
Level Order Traversal\nNote that this is not the most compact solution and that this does not use the special property of binary search tree. It\'s however simp
# Level Order Traversal\nNote that this is not the most compact solution and that this does not use the special property of binary search tree. It\'s however simple to implement and does the job.\n\nTo Serialize:\n* We traverse the BST in level order.\n* We use a separator and append the node values to our string. We use `blank` (i.e. `""`) character for the nulls to save some space.\n\nTo Deserialize:\n* We split the string by separator.\n* With the way we have serialized (we had also put nulls for all nodes) can use the binary tree property that for a parent at index `i`:\n  * the left child will be at position `2 * i + 1`\n  * the right child will be at position `2 * i + 2`\n* We construct the tree by using queue. We process parent nodes and enqueue child nodes and continue this process until queue is empty.\n\n```\npublic class Codec {\n    \n    public static final String SEPARATOR = ",";\n    public static final String EMPTY_STRING = "";\n\n    // Encodes a tree to a single string.\n    public String serialize(TreeNode root) {\n        \n        StringBuilder builder = new StringBuilder();\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n        \n        while(!queue.isEmpty()) {\n            \n            TreeNode node = queue.poll();\n            \n            if(node!=null) {\n                builder.append(node.val);\n                queue.offer(node.left);\n                queue.offer(node.right);\n            } else {\n                builder.append(EMPTY_STRING);\n            }\n            \n            // append separator\n            builder.append(SEPARATOR);\n        }\n        \n        // rmeove last space\n        builder.deleteCharAt(builder.length() - 1);\n        \n        return builder.toString();\n    }\n\n\n    // Decodes your encoded data to tree.\n    public TreeNode deserialize(String data) {\n\n        String[] values = data.split(SEPARATOR);\n        if(values[0].equals(EMPTY_STRING)) {\n            return null;\n        }\n\n        TreeNode root = new TreeNode(Integer.valueOf(values[0]));\n\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n       \n        int parentIndex=0;\n        while(!queue.isEmpty()) {\n            \n            TreeNode parent = queue.poll();\n\n            int leftChildIndex = 2 * parentIndex + 1;\n            int rightChildIndex = 2 * parentIndex + 2; \n            \n            if(leftChildIndex < values.length) {\n                if(values[leftChildIndex].equals(EMPTY_STRING)) {\n                    parent.left = null;\n                } else {\n                    int val = Integer.valueOf(values[leftChildIndex]);\n                    TreeNode leftChild = new TreeNode(val);\n                    parent.left = leftChild;\n                    queue.offer(leftChild);\n                }\n            }\n\n            if(rightChildIndex<values.length) {\n                if(values[rightChildIndex].equals(EMPTY_STRING)) {\n                    parent.right = null;\n                } else {\n                    int val = Integer.valueOf(values[rightChildIndex]);\n                    TreeNode rightChild = new TreeNode(val);\n                    parent.right = rightChild;\n                    queue.offer(rightChild);\n                }            \n            }\n\n            parentIndex++;    \n        }\n        \n        return root;\n    }\n}\n```
[]