Designing a File System Using Tree Structures

The scenario is that a software development team is building a new operating system for embedded devices, such as smart thermostats and wearable health monitors. One of the system’s core components is the file management module, which must efficiently organize and access files while using minimal memory and processing power.

To meet these requirements, the team decides to implement the file system using a binary tree.

Task 1

Design a binary tree that represents the following directory structure:

• Root: /home
  • o /home/user
    • documents
    • photos
  • o /home/system
    • logs
    • config

Task 2

Explain how the system would search for the file /home/user/photos/image1.jpg. What traversal method is used, and what is the time complexity?

Task 3

The system uses a decision tree to determine whether a user can access a file. The conditions are:

• Is the user authenticated?
• Does the user have read permission?
• Is the file marked as private?

Construct a decision tree that grants access only if the user is authenticated, has read permission, and the file is not private.

Task 4

A new folder named projects has been added under /home/user

• Describe how the insertion operation updates the tree and maintains its structure.

Task 5

The team wants to ensure that search operations remain efficient as the number of files grows. What strategies can be used to keep the tree balanced, and how do they affect complexity?