If nobody is allowed to add subfolders, then you can just cache the ID of the deepest node.
But, I'm assuming there must be someone that can add nodes to the tree, so the deepest node must change periodically. It all really depends on how often it changes. If it is only every 10 times you want to do an upload, then maybe you should cache the ID, and have a periodic job that goes recursively through the folder structure, and gets the new deepest folder ID. That's your option b, and unless you're really unusual, most accounts do not have any folder that is more than 8 levels deep. You can also recurse through the folder structure with more than one thread, if you need to optimize your performance.