Search a Folder Hierarchy with Extensible Document Filters

Implement an extensible search over a hierarchy of folders and documents. Initially find documents above a size threshold; then add document-type filtering and combine size AND type conditions.

Implement search_documents(nodes: string[][], root: string, minimumSize: int, allowedTypes: string[]) -> string[].

Constraints & Assumptions

This table representation and output order are explicit practice choices for the reported in-memory hierarchy.

• Each node is [id,parentId,kind,size,type], with unique nonempty ASCII IDs. Kind is FOLDER or DOCUMENT.
• The supplied nodes form one finite rooted tree with root's parentId empty. Every other parent exists and is a folder. Documents have no children. A folder's children are either all folders or all documents, matching the reported hierarchy; empty folders are valid.
• Folder size and type fields are empty. Document size is a decimal integer from 0 through 1000000000 and type is a nonempty case-sensitive string.
• At most 100000 nodes. Root is the tree's folder root. 0 <= minimumSize <= 1000000000.
• Match a document only when its size is strictly greater than minimumSize and, if allowedTypes is nonempty, its type belongs to that list. An empty allowedTypes list disables the type filter. Duplicate allowed types have no effect.
• Traverse children in their order of appearance in nodes and return matched document IDs in depth-first traversal order. Do not rely on the input rows already being in traversal order.

Example

nodes = [["root","","FOLDER","",""],["f","root","FOLDER","",""],
 ["a","f","DOCUMENT","100","pdf"],["b","f","DOCUMENT","200","txt"],
 ["c","f","DOCUMENT","300","pdf"]]
root = "root", minimumSize = 100, allowedTypes = ["pdf"]
result = ["c"]

Discuss how the traversal can depend on a document-predicate interface so adding a filter does not rewrite the walk. Explain an AND-combinator for predicates and test the threshold boundary, empty folders, deep trees, absent types, and combinations. The console function implements the two specified filters; a generalized public predicate API is a design extension.

Hint: Separate walking from deciding

The tree walk determines which documents are visited. A predicate determines which visited documents are returned.

Search a Document Hierarchy with Size and Type Filters

Approach

Build a node lookup and append each child ID to its parent list while reading rows. This records sibling order even when the parent row appears later or rows from separate subtrees interleave. Traverse from root using an explicit stack, pushing each folder's children in reverse list order so they are popped in forward depth-first order. For a document, apply size > minimumSize AND the optional membership predicate. Converting allowed types to a set removes duplicates; an empty set disables that condition. Every node is reached once because the input is a tree. This separates traversal from the decision to emit a document: a general predicate interface could expose a matches(document) method, and an AND combinator would short-circuit across component predicates, without changing the walk. That interface is a design extension; this callable implements only the two specified predicates. For n nodes and a allowed-type entries, expected time is O(n+a) plus input/output string work, and space is O(n+u) lookup/adjacency/set/stack entries for u distinct allowed types. The explicit stack handles deep trees.

• Time complexity: O(n + len(allowedTypes)) expected plus string processing
• Space complexity: O(n + distinct allowed types) entries plus strings and output