Katkat
Back

Recover a Rooted Tree from Depth-Annotated Preorder

GrammarlySoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Reconstruct a general ordered tree from its depth-annotated preorder traversal string and return it as a nested tuple.

Problem Statement

You are given a string traversal representing the preorder traversal of a rooted tree with an arbitrary number of children per node.

In this representation, each node is encoded as a sequence of zero or more hyphens '-' followed by the node's integer value:

  • The number of hyphens indicates the depth of the node (0-indexed). The root node has 0 hyphens (depth 0).
  • The integer value can contain multiple digits.
  • Children of any node appear in their natural left-to-right order immediately following the node in the preorder traversal.

Reconstruct the tree and return it as a canonical nested tuple structure where each node is represented as:

(value, (child_1, child_2, ...))

If a node has no children, its second element must be an empty tuple ().

Function Signature

def recover_tree(traversal: str) -> tuple:
    pass

Examples

Example 1

Input: traversal = "1-2--3--4-5"
Output: (1, ((2, ((3, ()), (4, ()))), (5, ())))

Explanation:

  • Root is 1 (depth 0).
  • 1 has children 2 (depth 1) and 5 (depth 1).
  • 2 has children 3 (depth 2) and 4 (depth 2).
  • 3, 4, and 5 have no children.

Example 2

Input: traversal = "10-20--30-40"
Output: (10, ((20, ((30, ()),)), (40, ())))

Explanation:

  • Root is 10.
  • Node 20 has child 30.
  • Node 40 is a sibling of 20 at depth 1.

Constraints

  • 1 <= len(traversal) <= 10^5
  • Node values are non-negative integers between 0 and 10^9.
  • The depth of a node is at most 1 greater than the depth of the node immediately preceding it.
  • traversal is guaranteed to be non-empty and well-formed according to the rules above.

Hints

Hint 1

Parse the string iteratively by counting consecutive hyphens to determine depth, followed by reading consecutive digits to parse the node value.

Hint 2

Use a stack to maintain the path from the root to the most recently visited node.

Hint 3

Because a node at depth d is always a child of the ancestor at depth d - 1, pop from the stack until its size equals d, then append the new node to the current top.

Follow-up questions

  • How would you serialize this nested-tuple tree back into the depth-annotated preorder string?
  • How would you modify your solution to validate malformed input, such as depth jumping by more than 1 or leading hyphens before the root?
  • If node values could be arbitrary alphanumeric strings with escaped hyphens, how would you adapt your parser?