Design a serialization format for a binary tree and implement serialization and deserialization so that decoding an encoded tree preserves every node value and the exact left/right structure.
### Constraints & Assumptions
Use integer node values, including duplicates and negative values. The representation may be your choice; the required property is a faithful round trip, including the empty tree.
### Clarifying Questions to Ask
- Can values repeat, and how will the format distinguish a null child from a node value?
- Can tree depth exceed the language's recursion limit?
```hint Missing children carry information
A traversal of values alone can lose the distinction between a left child and a right child.
```
### What a Strong Answer Covers
- An unambiguous encoding of node values and null children.
- Matching traversal orders during writing and reading.
- Empty trees, duplicate values, skewed trees, and malformed input handling.
### Follow-up Questions
- How would you avoid recursion for a very deep tree?
- What additional rule would be needed if node values were arbitrary strings?
Overview: Serialize and deserialize binary trees with explicit null markers, preserving duplicate values and child structure while handling malformed input.
Design a serialization format for a binary tree and implement serialization and deserialization so that decoding an encoded tree preserves every node value and the exact left/right structure.
Constraints & Assumptions
Use integer node values, including duplicates and negative values. The representation may be your choice; the required property is a faithful round trip, including the empty tree.
Clarifying Questions to Ask Guidance
Can values repeat, and how will the format distinguish a null child from a node value?
Can tree depth exceed the language's recursion limit?
What a Strong Answer Covers Guidance
An unambiguous encoding of node values and null children.
Matching traversal orders during writing and reading.
Empty trees, duplicate values, skewed trees, and malformed input handling.
Follow-up Questions Guidance
How would you avoid recursion for a very deep tree?
What additional rule would be needed if node values were arbitrary strings?