Turning a Flat Comment List into Threaded Replies

Question

Convert a flat list of comments carrying parentId values into a nested tree where each comment has a children array, then render that tree with indentation by depth. Roots are shown newest first.

Bobyard interview candidates · Answer

Problem The API returns comments as a flat array in which each record carries an optional parentId. Convert it into a nested structure where every comment has a children array, and then render the nested result in a UI with visible indentation. - A comment with parentId: null is a root. - Each other comment is attached under the comment whose id equals its parentId. - All original fields (content, createdAt, and so on) must survive the conversion. - Roots are presented newest first by createdAt. - Decide, and state, what happens to a comment whose parent is not in the input. Examples Input: Output: a single root (id 1) whose children holds comment 2, whose children holds comment 3. The component that renders the tree is a recursive React component taking comment and depth, which indents each level by a fixed number of pixels. Hints 1. You need a way to jump straight from a parentId to the node that represents that parent, without scanning the array to find it. 2. Index every comment by id in a Map, with each value already carrying an empty children array. A second pass can then attach nodes to parents in constant time. 3. First pass populates the map. Second pass: a null parentId goes to roots; otherwise push onto the parent's children. If the parent lookup fails, treat the node as a root. Approach Begin with the brute force so something is on the board: for each comment, scan the whole array for its parent and push the comment onto that parent's children, or onto roots when no parent exists. It is correct but O(n^2), which grows quickly as the number of comments increases. The bottleneck is the repeated parent search. Pre-index by id so a parent lookup becomes O(1). A Map is the natural structure because keys can be numbers, strings or UUIDs. The plan: pass one creates, for each comment, a node that spreads the original fields and adds children: [], and stores it in the map. Pass two walks the original array again, fetches each node, and either pushes it to roots or appends it to its parent's children. Settle the orphan case before coding. A parent may have been deleted, filtered out, or the data may be malformed. Dropping such a comment silently loses user content, so promoting it to a root is the safest default; say so to the interviewer and move on. Sorting is a presentation step. Sort roots by createdAt descending once the tree is built, rather than trying to maintain order while linking; if children also need ordering, sort each children array after pass two. Rendering is a recursive component: render the comment's own content, then map over children with depth + 1, using marginLeft: depth 20 for indentation and key={child.id} for reconciliation. Solution Time: O(n) for the two passes plus O(r log r) for sorting the r roots; Map operations are O(1). Space: O(n) for the map and the node objects. Correctness: after pass one every input id has exactly one node with empty children. Pass two visits each comment once and appends its node to at most one place, so the result is a forest in which every node appears exactly once, every edge is a parentId relationship from the input, and the roots are exactly the comments with no valid parent. Pitfalls - Scanning the array for each parent (find inside a loop) quietly makes the solution quadratic. - Linking in a single pass fails when a reply appears before its parent in the array; that is why the index is built first. - Copying only id and content into the node breaks the renderer as soon as it needs createdAt, author or votes. - Dropping orphans loses user content. - Mutating the input objects instead of copying them can surprise callers. - Using a plain object as the index risks key problems such as proto . - Pathologically deep threads can overflow the call stack in a recursive renderer. Talking Points 1. Announce the two-pass structure before coding: indexing by id turns an O(n^2) problem into O(n) and shows deliberate optimization. 2. Use a Map rather than a plain object, because ids can be numbers, strings or UUIDs and there are no prototype-key surprises. 3. Make the orphan decision explicit (promote, skip or throw) and justify promoting as avoiding data loss. 4. Spread the original comment so every field the API returns is preserved. 5. Mention recursion depth for rendering and say you would switch to an explicit stack for pathological inputs. 6. Sorting belongs after construction because it is a presentation concern; sort each children array too if needed. Follow-ups 1. Sort the whole tree by createdAt descending at every level. — Sort each children array after construction, or sort the flat list first and rely on stable insertion order. 2. The input is too large to hold as one tree in memory. — Store the flat list with a parent id column and query with a recursive CTE or a closure table. 3. Render without recursion to survive very deep threads. — Use an explicit stack of { node, depth } pairs, pushing children in reverse order. 4. Comments can be edite

Problem

Examples

Hints

Hint 1

Hint 2

Hint 3

Approach

Solution

Pitfalls

Talking Points

Follow-ups

Sort the whole tree by createdAt descending at every level.

The input is too large to hold as one tree in memory.

Render without recursion to survive very deep threads.

Comments can be edited or deleted after the tree is built.

Add pagination or lazy loading for replies.

Preparation

Comments