I recently needed something like this (and ended up rolling my own) while using the Dropbox API.

There have a fairly conservative rate limit, so you have to think about every API call you make. When traversing, it makes the most sense to do a recursive "ls" of the entire directory tree, keep it in memory, and perform whatever other actions you want (search, list, etc.) on the cached tree.

The implementation ended up being a pretty simple IDictionary<string, string[]>, but it would be interesting to try switching to something purpose-built.