Serialize and Deserialize Binary Tree Hard 0 attempts
LeetCode ↗

Serialize and Deserialize Binary Tree

Hard TreeBinary TreeDFS LeetCode

Design a way to encode a binary tree into a single string (serialization) and then reconstruct the exact same tree structure from that string (deserialization). The encoding scheme is entirely up to you — it just needs to round-trip correctly for any tree, including ones with null children.

Input Format
Implement codecRoundTrip(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement. Returned trees are displayed as level-order arrays, trimming trailing nulls.

Sample Input and Output

Example 1 · Run Sample

Input
root = [1,2,3,null,null,4,5]
Output
[1,2,3,null,null,4,5]

Example 2

Input
root = []
Output
[]
Constraints
  • 0 <= number of nodes <= 10^4
  • -1000 <= Node.val <= 1000
Test Cases (2)
Case 1
Args: [[1,2,3,null,null,4,5]] Expected: [1,2,3,null,null,4,5]
Case 2
Args: [[]] Expected: []
Topics
TreeBinary TreeDFS

Iterative Preorder with Null Markers

Serialize nodes in preorder, recording a null marker for every missing child so shape is preserved. To deserialize, track each unfinished node and whether its next child is left or right. Both operations use explicit stacks, so a long chain does not overflow the JavaScript call stack.

javascript
function serialize(root) {
  const stack = [root], values = [];
  while (stack.length) {
    const node = stack.pop();
    if (!node) values.push('null');
    else { values.push(String(node.val)); stack.push(node.right, node.left); }
  }
  return values.join(',');
}
function deserialize(data) {
  const values = data.split(',');
  if (values[0] === 'null') return null;
  const root = {val:Number(values[0]),left:null,right:null}, stack = [[root,0]];
  for (let i = 1; i < values.length; i++) {
    const frame = stack[stack.length-1], side = frame[1]++ === 0 ? 'left' : 'right';
    if (frame[1] === 2) stack.pop();
    const node = values[i] === 'null' ? null : {val:Number(values[i]),left:null,right:null};
    frame[0][side] = node;
    if (node) stack.push([node,0]);
  }
  return root;
}
function codecRoundTrip(root) {
  return deserialize(serialize(root));
}

Time: O(n) | Space: O(n), including the encoded string and reconstructed tree.

The editor calls codecRoundTrip to check the composition of both operations. Any serialization format that reconstructs the same tree is accepted.

Saved in this browser only. Private to you.

JavaScript