Serialise a binary tree to a string and reconstruct exactly the same tree from it. What has to be in the string?

What a traversal loses

The first instinct is to emit a traversal, and it is worth showing the interviewer immediately why one traversal is not enough, with the smallest possible pair of trees.

Take a root holding 1 with a single left child holding 2. Its preorder walk is 1 then 2. Now take a root holding 1 with a single right child holding 2. Its preorder walk is also 1 then 2. Two different trees, one token sequence, so the sequence cannot determine the tree. The same collision happens in postorder and in inorder. What has been lost is not the values and not their order; it is the shape, specifically which of a node's two child slots is occupied.

That diagnosis points straight at the fix. If the string records every child slot, including the empty ones, the shape is recoverable. A preorder walk that emits a marker for each absent child is unambiguous, and it is unambiguous for a reason worth stating: at every point in the reading, the number of tokens still owed is determined by the structure already read, so there is never a choice to make.

Preorder with explicit markers

Write the node's value, then serialise the left subtree, then the right, and emit a marker instead of descending when a child is absent.

private static final String NIL = "#";
private static final String SEP = ",";

void write(TreeNode node, StringBuilder out) {
    if (node == null) {
        out.append(NIL).append(SEP);   // the marker is what makes the shape recoverable
        return;
    }
    out.append(node.val).append(SEP);
    write(node.left, out);
    write(node.right, out);
}

The tree with root 1 and a left child 2 now serialises as 1,2,#,#,#, and the version with the right child as 1,#,2,#,#,. The two are distinct, which is the entire requirement.

Level-order with markers works equally well and is what most published test formats use, because it is readable by eye. The reason to prefer preorder in an interview is that the reader is the same recursion as the writer, so if you can argue one correct you have argued both.

Reading it back with one shared cursor

The reader mirrors the writer exactly: take the next token, and if it is the marker return null, otherwise build a node from it and then recursively build the left subtree and the right, in that order.

TreeNode read(Deque<String> tokens) {
    String token = tokens.poll();          // shared cursor: every call consumes from the same queue
    if (NIL.equals(token)) return null;
    TreeNode node = new TreeNode(Integer.parseInt(token));
    node.left = read(tokens);              // must be left first, matching the writer
    node.right = read(tokens);
    return node;
}

Two things in those five lines are where implementations fail. The first is that the cursor must be shared across the whole recursion. Passing an integer index by value into the recursive calls does not work, because the left subtree consumes an unknown number of tokens and the right subtree needs to start after them; the caller has no way to know how many were used unless the position is held in something the callee mutates. A queue, an iterator, or an index wrapped in a single-element holder all work; a plain int parameter does not.

The second is the order. The writer emitted left before right, so the reader must assign left before right, and in a language with unspecified argument evaluation order you must not fold both calls into a single constructor invocation. Writing the two assignments as separate statements makes the order part of the program rather than part of the language's discretion.

Both directions are O of n in time, visiting every real node once and every null slot once, which is n plus 1 markers for n nodes. Space is O of n for the output and O of h for the recursion, where h is the height.

Why two traversals is the worse answer

Candidates who know that preorder plus inorder determines a tree often offer that instead, and it is weaker for three reasons. It requires all values to be distinct, because reconstruction locates the root's value inside the inorder sequence and a duplicate makes that position ambiguous. It emits twice as many value tokens, against one marker per empty slot for the single-traversal version. And it needs an index of value to position to avoid a linear search at every level, which is more moving parts than one shared cursor.

Say all three briskly rather than dismissing the approach, because the pairing result is genuinely useful when the traversals are what you were given rather than what you chose to produce.

The details that bite outside the exercise

The delimiter has to be chosen against the value domain, not picked by habit. Integer values cannot contain a comma so a comma is safe for them; arbitrary strings can contain anything, and the answers are to escape the delimiter, to length-prefix each value, or to use a framing format that already solves this. Note that the marker has the same problem: # is only safe as a null marker if no value can serialise to #.

The other practical limit is depth. Both directions recurse to the height of the tree, and a tree built by inserting sorted keys into an unbalanced binary search tree has height equal to its node count, so a large degenerate tree overflows the stack in the reader as readily as in the writer. This is the case that makes the iterative follow-up a real question rather than a stylistic one: an explicit stack moves the depth cost onto the heap, where you can size it.

The information a traversal omits is the empty child slots, and every correct serialisation of a binary tree either writes them down or writes something else that implies them.