Encode and Rebuild a Binary Tree

Design two functions for a binary tree:

• encode(root) -> string
• decode(data) -> root

Each tree node contains an integer value and has up to two children.

Your encode function should convert a binary tree into a string representation. Your decode function should reconstruct an equivalent binary tree from that string.

Requirements:

• The reconstructed tree must have the same structure and node values as the original tree.
• The format may be any deterministic representation of your choice.
• Empty children must be represented in a way that allows exact reconstruction.
• You may assume node values fit in standard integer range.

Explain the data format you use and implement both functions.

Encode and Rebuild a Binary Tree

Design two binary-tree functions: encode(root) -> string and decode(data) -> root. The goal is to convert a binary tree into a deterministic string and then rebuild an equivalent tree from that string.

For this challenge, the input tree is given as a level-order Python list where None represents a missing child. Inside your solution, implement:

• encode(root): serialize the tree using preorder traversal
• decode(data): rebuild the tree from that serialized form

Use this exact deterministic format:

• Visit nodes in preorder: node, left subtree, right subtree
• Separate tokens with commas
• Use '#' to represent a null child

Example: Tree [1, 2, 3, None, 4] becomes '1,2,#,4,#,#,3,#,#'.

For automated checking, your function should:

1. Build the tree from the input level-order list
2. Encode it into a string
3. Decode the string back into a tree
4. Return a tuple: (encoded_string, rebuilt_tree_as_trimmed_level_order_list)

The rebuilt tree must match the original tree in both structure and node values.

Constraints

• 0 <= number of actual tree nodes <= 10^4
• Each node value is an integer in the standard 32-bit signed range
• The input list uses level-order representation with None for missing children
• The returned level-order list should not contain unnecessary trailing None values

Hints

1. A traversal by itself is not enough to rebuild the exact tree unless you also record missing children.
2. While decoding preorder data, think of each node as having two child slots to fill; a stack can help track whether the next token belongs to the left or right side.