Serialize and Deserialize Binary Tree

Write both directions of a tree codec based on preorder with null markers: each node is written as its value, followed by its left subtree, then its right subtree, and every missing child is written as #.

For example, the tree 1 2 3 null null 4 5 (level order) is serialised as 1 2 # # 3 4 # # 5 # #.

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input:

• line 1: serialize or deserialize
• line 2: for serialize, a tree in level order; for deserialize, a tree in the preorder # format

Output: for serialize, the preorder # string; for deserialize, the tree in level order.

Constraints: 0 ≤ nodes ≤ 10⁴, −1000 ≤ value ≤ 1000 (an empty tree is null in level order and # in preorder). The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: serialising is a preorder DFS that emits # for null. Deserialising reads the tokens in the same order: take a token — if it is # return null, otherwise make the node and build its left, then its right subtree. The # markers make the encoding unambiguous.