The only way I can think of doing this is by querying all Roles, then putting together a tree using the
ParentRoleId field. Is there a better way?
Here is an alternative method based on (extracted from) Find My Salesforce Users by Role Hierarchy by Jeff Douglas.
Is it better than your proposed solution? Probably not. It will depend on how many user roles there are and how deep the tree is. If you have a large number of UserRoles with very few levels of nesting it may be more efficient to make a couple of SOQL calls rather than retrieving all the roles and then rebuilding the entire tree.
And then you would get all the sub UserRoles for the parent UserRoleId with:
Just reread the question and picked up that you are using the Web Services API. You could still use exactly the same approach, but send the SOQL queries via SOAP rather than Apex.
It would pay to do some real world measurements about which performs best in your environment considering:
If you are only every interested in a subset of parent Ids and the nesting level is fairly shallow I'd look at just caching the values of interest and pulling them down with a few recursive calls. Otherwise, you will probably be better pulling all the possible data down in a query with possibly a follow up queryMore.