Quick Overview

Recover a binary tree from depth-encoded preorder using an ancestor stack, multi-digit parsing, left-child rules, and malformed-depth checks.

Recover a Binary Tree from Depth-Encoded Preorder

Company: Grammarly

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Recover a binary tree from its preorder encoding. Each node is written as D dashes followed by its nonnegative integer value, where D is its depth. The root has depth zero. If a node has only one child, that child is its left child. Return the reconstructed tree. For example, `1-2--3--4-5--6--7` describes a root 1 with children 2 and 5, and their respective children 3,4 and 6,7. ### Constraints & Assumptions This is the standard formulation of the named problem. Assume a nonempty valid encoding for the core task; describe how malformed depth changes could be rejected. ### Clarifying Questions to Ask - Can values have multiple digits, and is the one-child-is-left rule guaranteed? - Is malformed encoding validation required? ```hint Track the current ancestor path Before attaching a node of depth D, its parent must be the node at depth D-1 on the active path. ``` ### What a Strong Answer Covers - Parsing dash counts separately from multi-digit values. - Popping completed ancestors to the correct parent depth. - Left-before-right attachment and uniqueness under the one-child rule. ### Follow-up Questions - Why would recovery be ambiguous without the one-child-is-left rule? - How would you detect a depth jump that skips a parent?

Overview: Recover a binary tree from depth-encoded preorder using an ancestor stack, multi-digit parsing, left-child rules, and malformed-depth checks.

Reconstruct the binary tree encoded in `traversal`. The string lists nodes in preorder. A node at depth D is written as D dashes followed by its nonnegative integer value in decimal. The root is at depth zero. If a node has one child, that child is its left child. Return the reconstructed tree as a level-order list. Each non-null node contributes left and right child slots. Use null (`None` in Python) for missing children and omit trailing nulls. A null slot contributes no child slots of its own.

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

  1. A node with only one child contributes its value in the left-child slot.

Recover a Tree From Preorder Encoding

mediumGrammarlySoftware Engineer

Reconstruct the binary tree encoded in traversal. The string lists nodes in preorder. A node at depth D is written as D dashes followed by its nonnegative integer value in decimal. The root is at depth zero. If a node has one child, that child is its left child.

Return the reconstructed tree as a level-order list. Each non-null node contributes left and right child slots. Use null (None in Python) for missing children and omit trailing nulls. A null slot contributes no child slots of its own.

View full question (all parts)

Recover a binary tree from its preorder encoding. Each node is written as D dashes followed by its nonnegative integer value, where D is its depth. The root has depth zero. If a node has only one child, that child is its left child. Return the reconstructed tree.

For example, 1-2--3--4-5--6--7 describes a root 1 with children 2 and 5, and their respective children 3,4 and 6,7.

Constraints & Assumptions

This is the standard formulation of the named problem. Assume a nonempty valid encoding for the core task; describe how malformed depth changes could be rejected.

Clarifying Questions to Ask

  • Can values have multiple digits, and is the one-child-is-left rule guaranteed?
  • Is malformed encoding validation required?

What a Strong Answer Covers

  • Parsing dash counts separately from multi-digit values.
  • Popping completed ancestors to the correct parent depth.
  • Left-before-right attachment and uniqueness under the one-child rule.

Follow-up Questions

  • Why would recovery be ambiguous without the one-child-is-left rule?
  • How would you detect a depth jump that skips a parent?

Examples

Example 1
Input
('1-2--3--4-5--6--7',)
Output
[1, 2, 5, 3, 4, 6, 7]
Notes
All four grandchildren appear after the two children in level order.
Example 2
Input
('10-20--300-40--500---600',)
Output
[10, 20, 40, 300, None, 500, None, None, None, 600]
Notes
The null entries preserve absent right children and the absent children of 300.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def recover_tree_from_preorder(traversal) -> list[int | None]:
Sample call
recover_tree_from_preorder('1-2--3--4-5--6--7')
Language
Case 1
Input
('1-2--3--4-5--6--7',)
Expected
[1, 2, 5, 3, 4, 6, 7]
Case 2
Input
('10-20--300-40--500---600',)
Expected
[10, 20, 40, 300, None, 500, None, None, None, 600]

Browse More Questions

Show the approach

Approach

Parse each dash run as a depth and each digit run as one value. Keep a stack holding the path to the prior node. Pop until the path contains exactly D ancestors. When D is positive, the top is the new node’s parent, so attach to its left slot if free and to its right otherwise. Preorder visits the left child before the right and the single-child rule removes the final ambiguity. Push the new node to restore the path invariant. For malformed input, a skipped parent depth or a third child would invalidate the encoding.

Once built, visit the tree in breadth-first order, recording null slots only for the absent children of real nodes. Trim nulls beyond the final real node.

Time complexity:
O(L) for an encoding of L characters.
Space complexity:
O(N) auxiliary space for N nodes.