Q3 - The Comment Thread (Rebuilding the Reply Tree)

Scenario: A comment section is stored as a flat list of rows, one per comment. Each row is [id, parentId, timestamp]: a unique id, the id of the comment it replies to, and when it was posted. A top-level comment (a reply to the post itself, not to another comment) has parentId = -1. The author and text live elsewhere, keyed by id; here you work only with the structure.

Part 1. Return the threaded display order: the list of (id, depth) pairs in the exact order they render on screen. A comment is immediately followed by its replies (and their replies, recursively). Comments at the same level are ordered oldest first by timestamp, and any tie on timestamp breaks by smaller id. Top-level comments start at depth = 0.

Input:  comments = [[1,-1,10], [2,-1,30], [3,1,20], [4,1,40], [5,3,25], [6,2,35]]
Output: [(1,0), (3,1), (5,2), (4,1), (2,0), (6,1)]
Why: Comment 1 (top level) is followed by its replies 3 then 4 (3 is older).
        Reply 3 has its own reply 5, which nests one level deeper. Then top-level
        comment 2, followed by its reply 6.

Part 1: Rebuild the Tree, Then Walk It

The flat rows hide a tree, and rebuilding it takes three small steps.

Step 1: Group every comment under its parent

Make one pass over the rows and bucket each comment under its parentId. Now every comment can instantly find its direct replies, and the -1 bucket is special: it holds the top-level comments (a forest, since a post can have many).

group the 6 rows by parentId:

   parentId -1  ->  [1, 2]     the top-level comments
   parentId  1  ->  [3, 4]     replies to comment 1
   parentId  2  ->  [6]        replies to comment 2
   parentId  3  ->  [5]        replies to comment 3

Step 2: Sort each bucket oldest-first

Grouping kept whatever order the rows happened to arrive in, but on screen a comment's replies read oldest-first. So sort every bucket by (timestamp, id) (the id only breaks ties on identical timestamps). In this example the buckets already came out ordered, but the sort is what guarantees it in general. Suppose comment 1's two replies had been stored the other way around:

sort each bucket by (timestamp, id), oldest first:

   comment 1's replies, as grouped   ->  [4 @t40, 3 @t20]
   after sorting                      ->  [3 @t20, 4 @t40]     (3 is older, so it renders first)

Step 3: Walk the tree in pre-order

Now produce the display order. Visit a comment, emit (id, depth), then recurse into its replies. Emitting a comment before its replies is what makes a reply render directly beneath its parent, and passing depth + 1 down each level gives the indent. Here is the reconstructed tree, drawn so that reading it top to bottom is the answer:

1  @t10                     depth 0   (top level)
|__ 3  @t20                 depth 1   (reply to 1)
|   |__ 5  @t25             depth 2   (reply to 3)
|__ 4  @t40                 depth 1   (reply to 1)
2  @t30                     depth 0   (top level)
|__ 6  @t35                 depth 1   (reply to 2)

In code the walk is only a few lines: emit the node, then recurse into its already-sorted children one level deeper.

def visit(comment_id, depth):
    order.append((comment_id, depth))            # emit the comment BEFORE its replies
    for child in children_by_parent.get(comment_id, []):
        visit(child[0], depth + 1)               # then dive into each reply, one level deeper

The pre-order walk is the part worth seeing run. Step through it frame by frame: at each step the current comment is highlighted, it is emitted to the display order on the right, and the walk dives all the way into that comment's replies before moving to the next one.

1 / 7

Watch the interleaving in the frames above: comment 1 is emitted, then its entire subtree (3, then 5, then 4) before comment 2 ever appears. That is precisely why a plain timestamp sort fails, reply 4 (t40) is newer than comment 2 (t30), yet it must come first because it belongs to comment 1's subtree.

# O(n log n) time (sorting siblings) | O(n) space
ROOT = -1                                        # parentId of a top-level comment

def display_order(comments):
    children_by_parent = {}
    for comment_id, parent_id, timestamp in comments:
        children_by_parent.setdefault(parent_id, []).append((comment_id, parent_id, timestamp))
    for siblings in children_by_parent.values():
        siblings.sort(key=lambda c: (c[2], c[0]))    # oldest first; ties broken by id
    order = []
    def visit(comment_id, depth):
        order.append((comment_id, depth))            # pre-order: a comment before its replies
        for child in children_by_parent.get(comment_id, []):
            visit(child[0], depth + 1)
    for root in children_by_parent.get(ROOT, []):
        visit(root[0], 0)
    return order

Part 2: How Many Replies Under Each Comment

With the thread rebuilt, the interviewer asks for the number every comment shows next to it: "N replies." For each comment, return the total number of comments in its subtree, excluding itself, so a top-level comment counts its replies, their replies, and so on, all the way down.

Input:  comments = [[1,-1,10], [2,-1,30], [3,1,20], [4,1,40], [5,3,25], [6,2,35]]
Output: {1: 3, 2: 1, 3: 1, 4: 0, 5: 0, 6: 0}
Why: Comment 1's subtree is {3, 4, 5}, so 3 replies. Comment 2 has just {6}, so 1.
        Comment 3 has {5}, so 1. Comments 4, 5, and 6 have no replies, so 0.

This is the same tree, walked the other way around: post-order. A comment's total is the sum over its direct replies of 1 (the reply itself) plus that reply's own total. The trick is that you compute a child's total before the parent's, so the numbers roll up from the leaves. Step through the roll-up frame by frame: each comment's count settles only after its replies are done, and you can watch the totals climb the tree (notice comment 1 add up its two replies once both are known).

The roll-up is one short post-order function: a comment's total is the sum over its replies of that reply plus everything nested under it.

def count_subtree(comment_id):
    total = 0
    for child in children_by_parent.get(comment_id, []):
        total += 1 + count_subtree(child[0])     # this reply, plus its own nested replies
    counts[comment_id] = total
    return total

1 / 7

Note that Part 2 does not need the sibling sort at all, the count of a subtree does not depend on the order you visit it in.

# O(n) time | O(n) space
ROOT = -1

def reply_counts(comments):
    children_by_parent = {}
    for comment_id, parent_id, timestamp in comments:
        children_by_parent.setdefault(parent_id, []).append((comment_id, parent_id, timestamp))
    counts = {}
    def count_subtree(comment_id):
        total = 0
        for child in children_by_parent.get(comment_id, []):
            total += 1 + count_subtree(child[0])     # this reply, plus its own nested replies
        counts[comment_id] = total
        return total
    for root in children_by_parent.get(ROOT, []):
        count_subtree(root[0])
    return counts

Complexity Analysis

• Part 1 (display order): O(n log n) time, dominated by sorting the sibling lists. Across the whole tree the sorts total O(n log n) in the worst case (one comment with all the others as direct replies); the grouping and the pre-order walk are each O(n). Space is O(n) for the map and the recursion.
• Part 2 (reply counts): O(n) time. No sort is needed, just one grouping pass and one post-order walk that touches every comment once. Space is O(n).
• Recursion depth is the length of the deepest reply chain. Comment threads are shallow in practice, but a pathologically deep chain would want an explicit stack instead of the call stack; worth naming to the interviewer.

Final Notes

1. Flat rows are a tree. The moment the input is [id, parentId, ...], group by parentId so every node knows its direct children. That one step turns a confusing list into a structure you can walk, and it is the whole setup for both parts.
2. Pre-order for display, post-order for counts. Emitting a comment before its replies produces the threaded order; computing a subtree total after its children rolls the counts up from the leaves. Knowing which walk fits which question is the reusable idea here.
3. Time orders siblings, not the thread. Sorting the flat list by timestamp is the trap, a reply can predate a later top-level comment yet still nest deep inside an earlier one. Sort within each sibling list only.
4. Pin down the ordering rule up front. Oldest-first with an id tie-break is one clean choice; real feeds sometimes show top-level comments newest-first while keeping replies oldest-first. State the rule you are coding to, because that decision, not the traversal, is where these go wrong. 🚀