Implement DeleteTree With Limited Filesystem APIs

Problem Statement

You are working with a remote storage client that provides only low-level filesystem operations. You need to implement a function delete_tree(fs: FileSystem, root_path: str) -> None that completely removes the file or directory located at root_path, including all nested files and subdirectories (equivalent to rm -rf).

The target filesystem enforces that a directory cannot be deleted unless it is completely empty.

Provided Interface

You are given an instance of FileSystem with the following methods:

class FileSystem:
    def is_directory(self, path: str) -> bool:
        """Returns True if path points to a directory, False if it is a regular file.
        Raises an error if path does not exist.
        """
        pass

    def list_dir(self, path: str) -> list[str]:
        """Returns a list of immediate child names (not full paths) within path.
        Raises an error if path is not a directory.
        """
        pass

    def delete_file(self, path: str) -> None:
        """Deletes a single file. Raises an error if path is a directory or does not exist."""
        pass

    def delete_directory(self, path: str) -> None:
        """Deletes an empty directory. Raises an error if path is not empty or does not exist."""
        pass

Function Signature

def delete_tree(fs: FileSystem, root_path: str) -> None:
    pass

Constraints

• The directory tree may contain up to 100,000 total items.
• Maximum depth of the tree can be up to 20,000. Solutions relying on standard recursive calls will trigger a stack overflow in languages with fixed recursion limits (such as Python).
• Paths are separated by /. Avoid trailing slashes in child paths (e.g., if parent is /a/b and child is c, the path is /a/b/c).
• root_path may point directly to a file rather than a directory.

Examples

Example 1:

/app
├── config.json
└── logs/
    └── app.log

Input: root_path = "/app" Execution order:

1. Delete /app/config.json (file)
2. Delete /app/logs/app.log (file)
3. Delete /app/logs (now empty directory)
4. Delete /app (now empty directory)

Example 2:

Input: root_path = "/app/config.json" Execution order:

1. Delete /app/config.json (single file deletion)