Level by level order · DSA Mastery

Scenario

A social feed shows a comment thread. Each comment has at most two replies, a left one and a right one. The page loads the thread one row at a time: first the top comment, then its replies, then the replies to those, and so on.

A thread can have up to 100,000 comments. The page needs the comment ids grouped by row, with each row listed from left to right.

Your task

Write thread_levels(values, left, right).

The comments are numbered 0 to n - 1, and comment 0 is the top comment.
values[i] is the id shown for comment i.
left[i] and right[i] are the numbers of the replies to comment i, or -1 where there is none.
Return a list of rows. Row 1 holds the id of the top comment. Row 2 holds the ids of its replies, the left one first. Each later row holds the ids of the replies to the comments in the row before, in the same left-to-right order.

Examples

Example 1 (traced)#

text2 lines

Input:  values = [10, 20, 30, 40, 50], left = [1, 3, -1, -1, -1], right = [2, 4, -1, -1, -1]
Output: [[10], [20, 30], [40, 50]]

Row	Comments in the row (left to right)	Replies, in order, for the next row
1	comment 0 (id `10`)	comments 1 and 2
2	comments 1 and 2 (ids `20`, `30`)	comments 3 and 4 (comment 2 has none)
3	comments 3 and 4 (ids `40`, `50`)	none: stop

Example 2#

text2 lines

Input:  values = [7], left = [-1], right = [-1]
Output: [[7]]

A thread of one comment is one row.

Example 3#

text2 lines

Input:  values = [1, 2, 3], left = [1, 2, -1], right = [-1, -1, -1]
Output: [[1], [2], [3]]

Each comment has one reply, so every row holds one comment.

Constraints

1 ≤ length of values = length of left = length of right ≤ 10^5
0 ≤ values[i] ≤ 10^6
every entry of left and right is -1 or a comment number from 1 to n - 1
the comments form one tree under comment 0

What does n ≤ 10^5 tell you?

A thread that is a chain of 100,000 replies is allowed, and it makes 100,000 rows. A solution that finds each row by scanning every comment costs the number of rows times n, which is about 10^10 steps for a chain.

Build each row from the row before it, and every comment is looked at once.

Scenario

A thread can have up to 100,000 comments. The page needs the comment ids grouped by row, with each row listed from left to right.

Your task

Write thread_levels(values, left, right).

The comments are numbered 0 to n - 1, and comment 0 is the top comment.
values[i] is the id shown for comment i.
left[i] and right[i] are the numbers of the replies to comment i, or -1 where there is none.
Return a list of rows. Row 1 holds the id of the top comment. Row 2 holds the ids of its replies, the left one first. Each later row holds the ids of the replies to the comments in the row before, in the same left-to-right order.

Examples

Example 1 (traced)#

text2 lines

Input:  values = [10, 20, 30, 40, 50], left = [1, 3, -1, -1, -1], right = [2, 4, -1, -1, -1]
Output: [[10], [20, 30], [40, 50]]

Row	Comments in the row (left to right)	Replies, in order, for the next row
1	comment 0 (id `10`)	comments 1 and 2
2	comments 1 and 2 (ids `20`, `30`)	comments 3 and 4 (comment 2 has none)
3	comments 3 and 4 (ids `40`, `50`)	none: stop

Example 2#

text2 lines

Input:  values = [7], left = [-1], right = [-1]
Output: [[7]]

A thread of one comment is one row.

Example 3#

text2 lines

Input:  values = [1, 2, 3], left = [1, 2, -1], right = [-1, -1, -1]
Output: [[1], [2], [3]]

Each comment has one reply, so every row holds one comment.

Constraints

1 ≤ length of values = length of left = length of right ≤ 10^5
0 ≤ values[i] ≤ 10^6
every entry of left and right is -1 or a comment number from 1 to n - 1
the comments form one tree under comment 0

What does n ≤ 10^5 tell you?

Build each row from the row before it, and every comment is looked at once.