Build Nested Comments from Parent References

Problem Statement

You are given a list of comments, where each comment contains an id, text, and an optional parent_id. Comments may arrive in any order; it is possible for a child comment to appear in the input before its parent.

Your task is to transform this flat list into a hierarchical forest structure. A parent node should contain a list of its children in the order they appear in the original input. You must also implement basic validation to return an error if a comment refers to a non-existent parent_id (a dangling reference) or if a circular dependency is detected.

Function Signature

def build_comment_tree(comments):
    # comments: List of dicts, e.g., {'id': 1, 'text': 'A', 'parent_id': None}
    # Returns: List of root nodes with nested 'children' lists
    # Raises: ValueError for dangling references or cycles

Examples

Example 1: Input: [{'id': 2, 'parent_id': 1}, {'id': 1, 'parent_id': None}, {'id': 3, 'parent_id': 1}] Output: [{'id': 1, 'parent_id': None, 'children': [{'id': 2, 'children': []}, {'id': 3, 'children': []}]}]

Example 2 (Dangling): Input: [{'id': 2, 'parent_id': 99}] Output: Raises ValueError because 99 does not exist.

Constraints

• Number of comments: N <= 10^5.
• You must process the data in linear time O(N).
• Preserve the relative order of children as found in the input list.