Problem Description

You need to design a file system that can create new file paths and associate integer values with them.

A valid path follows these rules:

• It starts with / followed by one or more lowercase English letters
• Multiple directories can be concatenated with / as separator
• Examples of valid paths: /leetcode, /leetcode/problems
• Invalid paths: empty string "", just /

Your FileSystem class should implement two methods:

1. createPath(path, value):

   • Creates a new path and associates it with the given integer value
   • Returns true if the path was successfully created
   • Returns false if:
     • The path already exists, OR
     • The parent path doesn't exist (e.g., trying to create /a/b/c when /a/b doesn't exist)

2. get(path):

   • Returns the integer value associated with the given path
   • Returns -1 if the path doesn't exist

The solution uses a Trie (prefix tree) data structure where:

• Each node stores a value (v) representing the value of that path
• Each node has children stored in a hash table, where keys are path segments and values are child nodes
• When inserting a path like /a/b/c, it splits by / and traverses through nodes a, then b, checking that parent paths exist before creating c
• When searching for a path, it traverses the trie following the path segments and returns the value at the final node

Intuition

When we think about file systems, they naturally form a tree-like hierarchy. Each directory can contain multiple subdirectories, and we navigate through them level by level using path separators (/). This hierarchical structure immediately suggests using a tree data structure.

The key insight is that we need to efficiently:

1. Check if parent paths exist when creating a new path
2. Navigate through the path components to store or retrieve values

A Trie (prefix tree) is perfect for this because:

• File paths share common prefixes (e.g., /leetcode and /leetcode/problems share /leetcode)
• We can traverse the trie level by level, matching each path segment
• Checking parent existence becomes natural - we just verify each node exists as we traverse

For the createPath operation, we can split the path by / and traverse the trie until we reach the parent of the target node. If any intermediate node doesn't exist, the parent path is missing, so we return false. If we successfully reach the parent and the target doesn't already exist, we create it.

For the get operation, we simply traverse the trie following the path segments. If we can reach the target node, we return its value; otherwise, we return -1.

The beauty of this approach is that both operations have time complexity proportional to the path length O(|path|), and the tree structure naturally enforces the parent-child relationships that the file system requires.

Learn more about Trie patterns.

Solution Approach

The solution implements a Trie data structure to represent the file system hierarchy. Let's walk through the implementation:

Trie Node Structure

Each [Trie](/problems/trie_intro) node contains:

• children: A dictionary/hash table where keys are path segment names and values are references to child Trie nodes
• v: An integer value associated with the current path (default is -1 for non-existent paths)

FileSystem Class Implementation

The FileSystem class maintains a root Trie node and delegates operations to it.

Creating a Path - insert(path, value)

1. Start from the root node
2. Split the path by / to get individual segments: ps = path.split("/")
3. Traverse through parent segments ps[1:-1] (excluding empty first element and last segment):
   • For each segment, check if it exists in current node's children
   • If any parent segment doesn't exist, return false (parent path missing)
   • Move to the child node
4. Check if the last segment ps[-1] already exists in current node's children:
   • If it exists, return false (path already exists)
   • Otherwise, create a new Trie node with the given value and add it as a child
5. Return true for successful creation

Getting a Value - search(path)

1. Start from the root node
2. Split the path by / and iterate through all segments path.split("/")[1:]:
   • For each segment, check if it exists in current node's children
   • If not found, return -1 (path doesn't exist)
   • Move to the child node
3. After traversing all segments, return the value node.v of the final node

Time and Space Complexity

• Time Complexity: Both createPath and get operations are O(n) where n is the length of the path string, as we need to split the path and traverse through each segment
• Space Complexity: O(m * k) where m is the total number of paths created and k is the average path length

The Trie structure efficiently handles the hierarchical nature of file paths while ensuring that parent-child relationships are maintained and validated during path creation.

Example Walkthrough

Let's walk through a simple example to illustrate how the Trie-based file system works.

Example Operations:

1. createPath("/a", 1) → returns true
2. createPath("/a/b", 2) → returns true
3. createPath("/a/b/c", 3) → returns true
4. createPath("/a/d", 4) → returns true
5. get("/a/b") → returns 2
6. createPath("/a/b", 5) → returns false (already exists)
7. createPath("/x/y", 6) → returns false (parent /x doesn't exist)

Step-by-step visualization:

Initial state: Root node (empty)

root

After createPath("/a", 1):

• Split path: ["", "a"]
• Traverse parent segments (none in this case)
• Create child "a" with value 1

root
 └── a (v=1)

After createPath("/a/b", 2):

• Split path: ["", "a", "b"]
• Traverse to parent "a" (exists ✓)
• Create child "b" under "a" with value 2

root
 └── a (v=1)
      └── b (v=2)

After createPath("/a/b/c", 3):

• Split path: ["", "a", "b", "c"]
• Traverse: root → a (exists ✓) → b (exists ✓)
• Create child "c" under "b" with value 3

root
 └── a (v=1)
      └── b (v=2)
           └── c (v=3)

After createPath("/a/d", 4):

• Split path: ["", "a", "d"]
• Traverse to parent "a" (exists ✓)
• Create child "d" under "a" with value 4

root
 └── a (v=1)
      ├── b (v=2)
      │    └── c (v=3)
      └── d (v=4)

When calling get("/a/b"):

• Split path: ["", "a", "b"]
• Traverse: root → a → b
• Return value at node "b": 2

When calling createPath("/a/b", 5):

• Split path: ["", "a", "b"]
• Traverse to parent "a"
• Check if "b" exists in "a"'s children: YES
• Return false (path already exists)

When calling createPath("/x/y", 6):

• Split path: ["", "x", "y"]
• Try to traverse to parent "x"
• "x" doesn't exist in root's children
• Return false (parent path missing)

This example demonstrates how the Trie structure naturally enforces the file system constraints: paths must be created hierarchically (parents before children), duplicate paths are rejected, and the tree structure allows efficient navigation for both insertion and retrieval operations.

Solution Implementation

Time and Space Complexity

Time Complexity:

For the createPath operation:

• Splitting the path by "/" takes O(|w|) where |w| is the length of the path string
• Iterating through path components ps[1:-1] takes O(n) where n is the number of components
• Each dictionary lookup/insertion is O(1) on average
• Overall for a single createPath: O(|w|)

For the get operation:

• Splitting the path takes O(|w|)
• Iterating through components and dictionary lookups takes O(n) where n is the number of components
• Overall for a single get: O(|w|)

For all operations across the FileSystem's lifetime with set of paths W:

• Total time complexity: O(∑_{w ∈ W}|w|)

Space Complexity:

The Trie structure stores:

• Each unique path component as a key in the dictionary
• A Trie node for each path component in all paths
• The total number of characters stored across all path components is bounded by the sum of all path lengths

For the set of all inserted paths W:

• Total space complexity: O(∑_{w ∈ W}|w|)

This accounts for storing all the path components and the Trie node structure, where the space used is proportional to the total length of all paths inserted into the system.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Root Path and Empty Segments

One of the most common mistakes is mishandling the split operation on paths. When you split a path like /a/b/c by /, you get ["", "a", "b", "c"] where the first element is an empty string. Many implementations forget to skip this empty string, leading to incorrect traversal.

Problematic Code:

# Wrong - includes empty string
path_components = path.split("/")
for component in path_components:  # This will process ""
    # Logic here

Correct Approach:

# Correct - skip the empty string
path_components = path.split("/")
for component in path_components[1:]:  # Skip first empty element
    # Logic here

2. Not Validating Parent Path Existence Before Creating

A critical requirement is that parent paths must exist before creating a child path. For example, you cannot create /a/b/c if /a/b doesn't exist. Some implementations only check if the final path exists but forget to verify all parent directories.

Problematic Code:

def insert(self, path: str, value: int) -> bool:
    current = self
    components = path.split("/")[1:]
  
    # Wrong - directly creates all intermediate nodes
    for component in components[:-1]:
        if component not in current.children:
            current.children[component] = TrieNode()  # Creates missing parents!
        current = current.children[component]
  
    # Only checks final component
    if components[-1] in current.children:
        return False
    current.children[components[-1]] = TrieNode(value)
    return True

Correct Approach:

def insert(self, path: str, value: int) -> bool:
    current = self
    components = path.split("/")[1:]
  
    # Check all parent paths exist first
    for component in components[:-1]:
        if component not in current.children:
            return False  # Parent doesn't exist, cannot create
        current = current.children[component]
  
    # Then check and create final component
    if components[-1] in current.children:
        return False
    current.children[components[-1]] = TrieNode(value)
    return True

3. Edge Case: Creating Root Path /

The problem states that / alone is invalid, but some implementations don't handle this edge case properly. When splitting / by /, you get ["", ""], which could lead to unexpected behavior.

Solution:

def createPath(self, path: str, value: int) -> bool:
    # Add validation for edge cases
    if not path or path == "/" or not path.startswith("/"):
        return False
    return self.trie_root.insert(path, value)

4. Confusing Node Value vs Path Existence

Some implementations use the node's value to determine if a path exists (e.g., checking if value == -1). This is incorrect because -1 could be a valid value that a user wants to store.

Problematic Code:

def search(self, path: str) -> int:
    # ... traverse to node ...
    if node.value == -1:  # Wrong assumption
        return -1  # Thinks path doesn't exist
    return node.value

Correct Approach: The existence of a path should be determined by whether the node exists in the parent's children dictionary, not by the node's value. The value -1 should only be returned when the path doesn't exist in the tree structure.