v9.1.1
Menu

Serialize and Deserialize Binary Tree

hardPROTrees & BFSAmazon DSA

Design an algorithm to serialize a binary tree to a string and deserialize it back.

Input: level-order array (comma-separated, 'null' for missing). Output: serialized then deserialized back to level-order.

Return the recovered tree's level-order values as a single string separated by spaces, with 'null' for missing children and trailing 'null' entries omitted. Return an empty string for an empty tree.

Example

Input
1,2,3,null,null,4,5
Output
1 2 3 null null 4 5
Reasoning
  • Input: 1,2,3,null,null,4,5 lists the tree level by level, left to right; each null is an empty child slot. Root 1 has children 2 and 3, node 2 has none, and node 3 has children 4 and 5: 5 nodes on 3 levels.
  • The round trip: the string encoding is your choice, but it must be lossless. If the two empty slots under 2 were lost, 4 and 5 would be rebuilt as children of 2 and the shape would change.
  • Output: the rebuilt tree, listed level by level with single spaces, is 1 2 3 null null 4 5: 7 entries, 5 values plus the 2 empty slots under 2.
  • Notice that the 4 empty child slots under 4 and 5 are omitted, since nothing follows them. That is why the tree 1,2 prints just 1 2.
  • Here the output is just the input with commas turned into spaces, because this input has no trailing empty slots.

Constraints

  • 0 <= number of nodes <= 10^4
  • -1000 <= Node.val <= 1000

More from Amazon DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.