LINQ query to find the end of a chain of nested data using entity framework

We are uploading some files to the server and saving their data in a database for access (in the server itself for security they receive a randomly generated name),the problem comes when we need to do some checks to see if a file or a folder already exists, as it stands now each folder has subfolders, and that subfolders can have subfolders and so on....Each Folder also has a "ParentfolderID" so we know which folder it belongs to (the root folder will have ParentfolderID == null), with that we can navigate up and down, the names of folder and files repeat themselves quite a lot so we can easily have this structure:

Root Folder> foldername 1> foldername 2> foldername 3> foldername 4> files

Root Folder> foldername 1> foldername 2> foldername 3> foldername 5> files

Root Folder> foldername 4> foldername 3> foldername 4> files

Root Folder> foldername 1> foldername 2> foldername 3> foldername 6> foldername 1> files

We have some folders that need to be uploaded that contains hundreds of folders and files with all kind of structures and names, but of course you cannot upload the same file twice, which triggers the problem:

We are having massive performance issues because at the moment what we are doing to see if a folder exists is:

1. Grab all the folders names from the path (for each folder).

2. See if the Root Folder contains the first folder of the path and then see if the result of that contains the next one and so on...

3. If at some point the folder do not exist we know that the files do not exist either so we can upload and create, if at the end of the line all folders exist we check if the files exist in the last folder.

4. Repeat for every folder.

to have this all working we have 3 tables: Folder, File and Document (which is the relationship table between Folder and File).

at the end the code ended up being something like this:

//we loop across each folder path to see if the files with that path are already there
//this code will repeat for every single folder that the user is currently uploading

 private List<string> CheckForExistingFiles(string folderPath, Folder currentFolder,string[] fileNames)
{
        var individualFolders = folderPath.Split('\\');
        var existingFiles = new List<string>();

        for (int i = 0; i < individualFolders.Count(); i++)
        {
            currentFolder = currentFolder.SubFolders.SingleOrDefault(x => x.Name == individualFolders[i]);

            if (currentFolder == null)
            {
                return null;
            }
        }

            //we know that the folder exists, now we check if this folder contains this file

            var filesThatAlreadyExist = this.context.Documents.Where(x => x.FolderId == currentFolder.Id && fileNames.Contains(x.File.Name)).Select(x=>x.Name);

            if (filesThatAlreadyExist.Any())
            {
                existingFiles.AddRange(filesThatAlreadyExist.ToList());
            }        

            return existingFiles;
}

This code is of course extremely inefficient, it loops across way too much data and do too many database trips to see if a folder is there, then we still need to check if we have a file with that name in that folder, and grabbing all the folders at the same time so it only goes too the database once is not good neither. We also have problems when we try to navigate the other way around to reach the "Root Folder" of a given folder, because then we need to loop backwards until we reach the Root Folder.

I told my manager that I wanted to change the data structure to add the full path to each folder and file so it would be super easy to compare if that path already exists and would simplify the whole process a lot, but he strongly disagrees because he says that all we need to navigate in any direction is already there, we just need to find an efficient way to do it, which is true but in every test I did I ended up with some sort of loop or taking way more data than I need so I do still wonder if store the full path of each folder and file makes more sense than having to put so much effort in looping across so much data.

What I need to achieve:

An efficient LINQ query where I can find "the end of the line" without having to loop across all the data to see if every single subfolder exists, so by having and array of string[] paths that look like this:

Root Folder\ foldername 1\foldername 2\foldername 3\foldername 4\ files

Root Folder\ foldername 1\foldername 3\foldername 6\ foldername 4\ files

I want to check if the file names already exist, so I want to grab the end of the nested data from Root Folder (the only one that is there for sure because the user is uploading to it anything else may or may not exist)