Recover a Rooted Tree from Depth-Annotated Preorder
Company: Grammarly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
# Recover a Rooted Tree from Depth-Annotated Preorder
A rooted, ordered tree was serialized by preorder traversal. Before each node value, the serializer wrote one `-` character for each level of depth. The root has depth `0`, and node values are nonnegative decimal integers. A node may have any number of children; their order is the order in which they appear in the traversal.
Recover the tree and return it in a canonical nested-tuple form:
- A leaf is `(value, ())`.
- A non-leaf is `(value, (child_1, child_2, ...))`.
## Function Contract
```python
def recover_preorder(traversal: str):
...
```
## Constraints
- `1 <= len(traversal) <= 10_000`
- `traversal` contains only digits and `-` characters.
- The serialization is valid: it contains one depth-0 root, and depth never increases by more than one between consecutive nodes.
- Node values may contain multiple digits.
- Do not use `eval` or regular-expression replacement to construct executable code.
## Example
```text
traversal = "1-2--3--4-5--6--7"
result = (
1,
(
(2, ((3, ()), (4, ()))),
(5, ((6, ()), (7, ()))),
),
)
```
Quick Answer: Reconstruct an ordered rooted tree from preorder text in which hyphen count encodes depth and values may have multiple digits. Return a canonical nested-tuple representation while handling arbitrary child counts and long valid inputs without evaluating generated code.
Implement recover_preorder(traversal). A rooted ordered tree was serialized in preorder, with one '-' per depth before each nonnegative decimal node value. Return the recovered tree as a canonical nested string: a node is [value,[child1,child2,...]], with no spaces. Normalize each decimal token to its integer spelling by removing leading zeroes while keeping one zero for value zero. Arbitrarily large values therefore remain exact. For example, the leaf token 0007 is represented as "[7,[]]".
Constraints
- 1 <= len(traversal) <= 10,000
- The input contains only digits and '-' characters and is a valid serialization.
- There is one depth-zero root and depth never increases by more than one.
- Node values may contain leading zeroes; canonical output removes them except that zero is written as 0.
- Return the no-space canonical nested string [value,[children...]].
- Do not use eval or regular-expression replacement to construct executable code.
Examples
Input: ("1",)
Expected Output: "[1,[]]"
Explanation: A lone root is a leaf.
Input: ("10",)
Expected Output: "[10,[]]"
Explanation: A multi-digit root is preserved.
Hints
- Scan each token into its depth and normalize its decimal value with an ordinary character loop.
- When the next depth is not deeper, close the previous node and every completed ancestor before opening the sibling.
- The valid preorder depths let you serialize the recovered structure iteratively.