# A level order traversal solution

• Idea is pretty simple: traverse the tree using level order traversal to serialize the non-null nodes. If a null node is seen, serialize it as "N" but not add it into the queue anymore.

Since all the leaf null nodes are offered into the queue once, I'm effectively ensuring that all non null nodes have exactly two children during deserialization.

This solution is less space efficient comparing with DFS solutions as the queue uses O(n) space.

public class Codec {

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

StringBuilder tree = new StringBuilder();
queue.offer(root);

while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
tree.append("N,");
}
else {
tree.append(node.val).append(',');
queue.offer(node.left);
queue.offer(node.right);
}
}
tree.deleteCharAt(tree.length()-1);
return tree.toString();
}

public TreeNode deserialize(String data) {
String[] nodes = data.split("\\,");
if (nodes.length == 1) return null;

TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
queue.offer(root);
int i = 1;           // starting from the second node if root is not null

while (i < nodes.length) {
TreeNode node = queue.poll();

String left = nodes[i++], right = nodes[i++];
if (!left.equals("N")) {
TreeNode lChild = new TreeNode(Integer.parseInt(left));
node.left = lChild;
queue.offer(lChild);
}
if (!right.equals("N")) {
TreeNode rChild = new TreeNode(Integer.parseInt(right));
node.right = rChild;
queue.offer(rChild);
}
}
return root;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.