Comment Thread Flatten
A discussion app stores comments as a tree (each comment has a list of reply comments). To render in chronological depth-first order, the server flattens the tree into a list where each comment is followed immediately by all its descendants, depth-first.
Problem
Given the root comment of a tree, return the list of comment IDs in pre-order (root first, then each child's subtree fully expanded before moving to the next sibling).
Input
Root node of a tree (root may be null). Each node has an integer id and a list of zero or more child nodes. 0 ≤ n ≤ 10^4 nodes total.
Output
A list of n integer IDs in pre-order. Empty list if root is null.
Constraints
- 0 ≤ n ≤ 10,000
- Tree depth may approach 10^4 (skewed)
- Order: parent first, then each child's subtree (left to right)
Examples
Example 1
Input
Root(1) with children [Root(2) with children [Root(4)], Root(3)]
Output
[1, 2, 4, 3]
Pre-order: 1, then subtree of 2 (which is 2, 4), then subtree of 3.
Example 2
Input
null
Output
[]
Empty tree → empty list.