Find root IDs and paths

You are given a collection of string blocks, each represented as a JSON object with fields {"id": string, "parentId": string | null}. A block is a root if it has no parent (parentId is null or the referenced parent does not appear).

1. Write a function that returns all root ids from the input.
2. Follow-up: given a target id, return the path of ids from its root to that id. Explain your approach, the data structures you use, and analyze time and space complexity.

Find Root IDs

You are given a collection of blocks, each an object with fields id (string) and parentId (string or null). A block is a root if it has no parent — that is, its parentId is null, OR the parentId references an id that does not appear anywhere in the input.

Return the list of all root ids, in the order the blocks are given.

Example

blocks = [
  {"id": "a", "parentId": null},
  {"id": "b", "parentId": "a"},
  {"id": "c", "parentId": "b"}
]
=> ["a"]

a has no parent, so it is a root. b and c both chain up to a, so they are not roots.

A block whose parentId points to an id that is not present (a dangling reference) is also a root.

Constraints

• 0 <= number of blocks <= 10^5
• Each id is a non-empty string and ids are unique.
• parentId is either null or a string (which may or may not match an existing id).
• Return roots in the order their blocks appear in the input.

Hints

1. First collect every block's id into a hash set so you can test 'does this parent exist?' in O(1).
2. A block is a root when parentId is null OR parentId is not in that set — handle the dangling-reference case explicitly.
3. Preserve input order by iterating the blocks a second time rather than iterating the set.

Path From Root To Target

Using the same block structure — each block has an id (string) and a parentId (string or null), where a missing/dangling parentId means the block is a root — implement the follow-up:

Given a targetId, return the path of ids from the target's root down to the target, inclusive.

Example

blocks = [
  {"id": "a", "parentId": null},
  {"id": "b", "parentId": "a"},
  {"id": "c", "parentId": "b"}
]
targetId = "c"
=> ["a", "b", "c"]

Walk upward from the target following parentId links until you reach a root (null parent or a dangling parent reference), collecting ids, then reverse so the result reads root → target. If targetId is not present in the input, return an empty list.

Constraints

• 0 <= number of blocks <= 10^5
• ids are unique, non-empty strings.
• parentId is null or a string; a dangling parentId marks a root.
• If targetId is not one of the block ids, return an empty list.
• The path is returned root-first, target-last.

Hints

1. Build a map id -> effective parent, normalizing both null and dangling parents to 'no parent' (None).
2. Walk upward from the target collecting ids until you hit a node with no parent, then reverse the collected list.
3. Guard against cycles with a visited set so a malformed input can't loop forever; also return [] up front when the target isn't present.