Convert Leveled Rich-Text Tokens into Nested Lists

Problem Statement

In rich-text editors like Figma, hierarchical bulleted and numbered lists are often stored as a flat stream of tokens, where each token has a display string and a nesting level (an integer starting at 1).

Write a function build_nested_list(tokens) that converts an ordered sequence of leveled tokens into a list of nested nodes representing the document structure.

Each node in the output should be an instance of ListItem:

class ListItem:
    def __init__(self, text: str):
        self.text = text
        self.children = []  # List of ListItem objects

Nesting Rules

1. Tokens with level == 1 are top-level items and must be added directly to the root output list.
2. A token with level > 1 is placed as a child of the most recent preceding token whose level is strictly less than its own (parent_level < current_level).
3. If multiple preceding items have levels smaller than the current token's level, it attaches to the deepest (most recent) such item.
4. If a token's level is greater than 1 but no preceding item has a smaller level (for example, the list starts at level 2), treat it as a root-level item.
5. Original token order must be preserved.

Function Signature

def build_nested_list(tokens: list[tuple[int, str]]) -> list[ListItem]:
    pass

Examples

Example 1

Input:

tokens = [
    (1, "Fruit"),
    (2, "Apple"),
    (2, "Banana"),
    (3, "Cavendish"),
    (1, "Vegetable")
]

Output: A list with two top-level ListItem objects:

• "Fruit"
  • children: "Apple", "Banana"
    • "Banana" has child "Cavendish"
• "Vegetable"
  • children: []

Example 2 (Multi-level jump)

Input:

tokens = [
    (1, "Title"),
    (3, "Deep note"),
    (2, "Section")
]

Output:

• "Title" has child "Deep note" (because "Title" is the closest ancestor with level < 3).
• "Section" is also a direct child of "Title" (since its level 2 drops back below "Deep note"'s level 3 but is greater than 1).

Constraints

• 0 <= len(tokens) <= 10^5
• 1 <= level <= 10^4
• text is a non-empty string with length up to 100.
• Expected time complexity: O(N) where N is the number of tokens.
• Expected auxiliary space complexity: O(N).