MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Print Folder Structure

Written By ## Print Folder Structure Introduction

The Print Folder Structure problem asks us to take an input of file paths and print out the files in each folder. This problem requires us to create a tree-like structure representing the folder hierarchy to make it easier for us to traverse.

## Print Folder Structure Problem

Given a list of file paths, print all of the files in each of the folders.

For example:

Input: files = [ "/webapp/assets/html/a.html", "/webapp/assets/html/b.html", "/webapp/assets/js/c.js", "/webapp/index.html" ]

## Output:

-- webapp -- assets -- html -- a.html -- b.html -- js -- c.js -- index.html

## Print Folder Structure Solutions

To solve this problem, we can create a tree-like structure to represent the folder hierarchy. We start with an empty root node and iterate through each file path. For each file path, we split it into individual folder names and traverse the tree from the root, creating new nodes as needed for each folder. By the end of it, we have a tree that represents the folder structure.

To print all the files in each folder, we use a depth-first search (DFS) approach. We define a recursive function that takes a current node and an indentation level. At each node, we print the folder name with the appropriate indentation. If the current node has children (sub-folders), we recursively call the function for each child, incrementing the indentation level. If a node does not have any children, it means it is a file, and we print it with the proper indentation.

``````class Node:
def __init__(self, name):
self.name = name
self.children = {}

class Tree:
def __init__(self):
self.root = Node("")

def insert_file(self, file_path):
folders = file_path.split("/")[1:]  # Exclude the empty root folder

current = self.root
for folder in folders:
if folder not in current.children:
current.children[folder] = Node(folder)
current = current.children[folder]

def print_files(self):
self._dfs_print(self.root, "")

def _dfs_print(self, node, indent):
if not node.children:
print(indent + "-- " + node.name)
return

print(indent + "-- " + node.name)
for child in node.children.values():
self._dfs_print(child, indent + "  ")

# Test case
files = [
"/webapp/assets/html/a.html",
"/webapp/assets/html/b.html",
"/webapp/assets/js/c.js",
"/webapp/index.html"
]

tree = Tree()
for file in files:
tree.insert_file(file)

tree.print_files()``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), where N is the number of file paths in the files input
• Space Complexity: O(M), where M is number of distinct folders in the path. We store each distinct folder as a node in the tree.