# Is it possible to get an O(1) space O(n) time algorithm?

• Here is my O(n)-O(n) solution, tl;dr

``````// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null)
return "N#";
StringBuffer sb = new StringBuffer();

while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode t = q.remove();
if (t == null) {
sb.append("N#");
}
else {
sb.append(Integer.toString(t.val) + "#");
}
}
}
return sb.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.charAt(0) == 'N')
return null;

int index = data.indexOf('#');

TreeNode root = new TreeNode(Integer.parseInt(data.substring(0, index)));
index += 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode t = q.remove();
// left child
if (data.charAt(index) == 'N') {
index += 2;
} else {
int next_index = data.indexOf('#', index);
TreeNode l = new TreeNode(Integer.parseInt(data.substring(index, next_index)));
index = next_index + 1;
t.left = l;
}
// right child
if (data.charAt(index) == 'N') {
index += 2;
} else {
int next_index = data.indexOf('#', index);
TreeNode r = new TreeNode(Integer.parseInt(data.substring(index, next_index)));
index = next_index + 1;
t.right = r;