Recover a Binary Tree from Depth-Encoded Preorder
Company: Grammarly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Overview: Recover a binary tree from depth-encoded preorder using an ancestor stack, multi-digit parsing, left-child rules, and malformed-depth checks.
Constraints
- The encoded tree is valid and nonempty. The string contains only ASCII digits and dashes and has at most 2^31 − 1 characters.
- Node values are integers from 0 through 2^53 − 1. The output list length is at most 2^31 − 1.
Examples
Input: ('1-2--3--4-5--6--7',)
Expected Output: [1, 2, 5, 3, 4, 6, 7]
Explanation: All four grandchildren appear after the two children in level order.
Input: ('10-20--300-40--500---600',)
Expected Output: [10, 20, 40, 300, None, 500, None, None, None, 600]
Explanation: The null entries preserve absent right children and the absent children of 300.
Hints
- A node with only one child contributes its value in the left-child slot.