Design an Iterative Path Tree and Clarify File Lookup Semantics

Problem Statement

In many distributed systems, managing file metadata requires representing hierarchical namespaces in memory without relying on recursive algorithms that risk call stack overflow on deeply nested structures.

Implement a FileSystemTree class that constructs an in-memory multi-way tree representing absolute file paths and supports searching for files by name.

Requirements

1. Component-based Representation: Each node represents a single path segment (directory or file name). Paths are absolute Unix-style paths (e.g., /a/b/file.txt). Adding a path implicitly creates any missing parent directories.
2. Iterative Search: Implement find_file(filename: str) -> list[str] to return the full absolute paths of all files matching filename. To handle arbitrarily deep file trees safely, the traversal must be iterative using an explicit stack, not recursive.
3. Ordering: Paths returned by find_file should be sorted in lexicographical order.

Class Interface

class FileSystemTree:
    def __init__(self):
        pass

    def add_path(self, path: str) -> None:
        """
        Inserts an absolute path into the tree.
        Creates implicit parent directories as needed.
        """
        pass

    def find_file(self, filename: str) -> list[str]:
        """
        Finds all full paths ending with the specified filename.
        Must traverse the tree iteratively using an explicit stack.
        """
        pass

Constraints

• Path strings start with / and contain lowercase English letters, digits, dots (.), and slashes (/).
• Consecutive slashes (e.g., //) are treated as a single slash; trailing slashes can be ignored unless referring to root /.
• Maximum number of added paths: 10^4
• Maximum depth of any path: 2000
• Maximum length of a single path: 10^5 characters.

Examples

Example 1

fs = FileSystemTree()
fs.add_path("/var/log/syslog")
fs.add_path("/var/log/nginx/access.log")
fs.add_path("/home/user/log/syslog")

fs.find_file("syslog")
# Output: ["/home/user/log/syslog", "/var/log/syslog"]

fs.find_file("access.log")
# Output: ["/var/log/nginx/access.log"]

fs.find_file("missing.txt")
# Output: []

Example 2

fs = FileSystemTree()
fs.add_path("/a/b/a/target.txt")
fs.add_path("/a/target.txt")

fs.find_file("target.txt")
# Output: ["/a/target.txt", "/a/b/a/target.txt"]

Edge Cases to Consider

• Duplicate directory names at different hierarchy levels (e.g., /a/b/a/c).
• Redundant insertions of the exact same path.
• Root-level files (e.g., /file.txt).
• File names matching directory names (clarify whether directories should be returned or only terminal leaves/files).