Filter nested comments and keep only matched nodes and their descendants

Filter Nested Comments Medium · Topics · Company Tags · Hints

You are given a forest of nested comment nodes. Each node has a string field content and a list of child nodes children. The root-level nodes are provided in an array roots, and the relative ordering of siblings within any child list represents the display order of the comments.

You also have a predicate function predicate(node) that returns true if the node should be kept based on some condition (for example, content contains a certain keyword, or a metadata field equals a particular value).

Write a function that returns a new forest of nodes such that:

• Any node for which predicate returns true, together with all of its descendants, is retained.
• Any node that is not kept by the rule above is removed entirely.
• The original sibling order is preserved for any nodes that survive the filtering process and remain under the same parent.

You may assume the total number of nodes across the forest is at most N. The target time complexity is O(N).

Example 1:

Input:
roots = [
  { content: "a", children: [
    { content: "b", children: [] },
    { content: "c", children: [] }
  ] }
]
predicate: node.content == "a"

Output: same tree as input (all nodes kept)

Explanation: Node "a" matches the predicate, so it and both of its descendants "b" and "c" are retained.

Example 2:

Input:
roots = [
  { content: "x", children: [
    { content: "y", children: [
      { content: "z", children: [] }
    ] },
    { content: "w", children: [] }
  ] }
]
predicate: node.content == "y"

Output: [
  { content: "y", children: [
    { content: "z", children: [] }
  ] }
]

Explanation: Node "y" matches, so it and descendant "z" are kept. Node "x" and "w" are discarded because they are not matches and are not descendants of a match. "y" becomes a new root.

Example 3:

Input:
roots = [
  { content: "p", children: [
    { content: "q", children: [] },
    { content: "r", children: [] }
  ] },
  { content: "s", children: [
    { content: "t", children: [] }
  ] }
]
predicate: node.content == "r" or node.content == "s"

Output: [
  { content: "r", children: [] },
  { content: "s", children: [
    { content: "t", children: [] }
  ] }
]

Explanation: "r" matches and has no children, so it is kept as a root. "s" matches, so it and descendant "t" are kept as a separate root. "p" and "q" are removed.

Constraints:

• 0 <= total nodes <= 50,000
• Each node's content is a string possibly containing any characters
• The predicate evaluates in O(1) per node
• Target time complexity: O(N) where N is the total number of nodes
• Target space complexity: O(N) (excluding output space for the filtered tree)