Build an Event-Driven Folder Browser

The Problem: Event-Driven Folder Browser

You are building the core engine for an interactive, recursive folder browser. You must design a state model and the necessary helper functions to manage a tree of folders. Each folder has a unique id, a name, an optional parentId, and an array of children (subfolders).

Requirements

1. Data Model: Define a structure that allows O(1) or O(log n) lookup of any folder by ID.
2. Operations: Implement the following functions:
   • addFolder(parentId, name): Adds a new folder and returns the new state.
   • moveFolder(folderId, newParentId): Moves a folder to a new parent. This must include an invalid-cycle prevention check (a folder cannot be moved into its own descendant).
   • deleteFolder(folderId): Removes a folder and its entire subtree.

Interface

# Example state structure
# state = { 'folders': { 'id': { 'id': '...', 'name': '...', 'parentId': '...', 'children': [] } }, 'rootIds': [...] }

def add_folder(state, parent_id, name):
    pass

def move_folder(state, folder_id, new_parent_id):
    pass

def delete_folder(state, folder_id):
    pass

Constraints

• The tree depth is unbounded.
• The number of operations can reach 10,000.
• Avoid unnecessary deep cloning of the entire state; prefer immutable updates or a normalized state structure.

Example

Input: Move folder 'B' into folder 'C', where 'C' is a child of 'B'. Output: Operation must be rejected (Cycle detected).

Edge Cases

• Moving a folder to its existing parent.
• Deleting the root folder.
• Renaming a folder while it is being dragged or moved.