Create Directory Structure

You are given a list of file paths. Each path is a string that represents the location of a file in a directory hierarchy, with levels separated by the '/' character. Your task is to organize these file paths into a hierarchical structure similar to a directory tree.

In the resulting structure, directories are represented as nested JSON objects and files are denoted by a null value. For example, a file file.txt in a directory dir would be represented as {"dir": {"file.txt": null}}.

The algorithm should ideally work in \(O(n)\) time on the number of file paths provided.

inputFormat

The first line contains an integer \(n\), the number of file paths. The following \(n\) lines each contain a non-empty string representing a file path, with levels separated by the '/' character.

outputFormat

Output a JSON object representing the derived hierarchical directory structure. Directories are represented by nested JSON objects, and files are represented with a null value. The JSON keys should appear in sorted order.

4
dir1/file1.txt
dir1/file2.txt
dir2/file3.txt
file4.txt

{"dir1":{"file1.txt":null,"file2.txt":null},"dir2":{"file3.txt":null},"file4.txt":null}