Build a Nested Comment Tree from a Flat List

Given a list of comment objects, each object contains: id: a unique integer comment ID. parent_id: the ID of its parent comment; null for a root comment. text: the comment content. Convert this flat list into a nested comment forest and return an array containing all root comments. Requirements: Preserve all original fields on every comment object. A comment with direct replies must contain a new children field holding an array of its direct child comments. Leaf comments do not need a children field. Root comments are those whose parent_id == null. Preserve the relative input order among root comments and among children of the same parent. All id values are unique, and every non-null parent_id refers to a valid comment in the input. Example input: [ {"id": 1, "parent_id": null, "text": "This is the first root comment."}, {"id": 2, "parent_id": null, "text": "This is the second root comment."}, {"id": 3, "parent_id": 1, "text": "Reply to the first root comment."}, {"id": 4, "parent_id": 2, "text": "Reply to the second root comment."}, {"id": 5, "parent_id": 3, "text": "Reply to the first reply on the first root comment."} ] Expected output: [ { "id": 1, "parent_id": null, "text": "This is the first root comment.", "children": [ { "id": 3, "parent_id": 1, "text": "Reply to the first root comment.", "children": [ { "id": 5, "parent_id": 3, "text": "Reply to the first reply on the first root comment." } ] } ] }, { "id": 2, "parent_id": null, "text": "This is the second root comment.", "children": [ { "id": 4, "parent_id": 2, "text": "Reply to the second root comment." } ] } ] Let n be the number of comments. Target O(n) time and O(n) extra space. Example Input [] Output []