Sounds like your using the beta endpoint rather then production eg
rather then
https://graph.microsoft.com/v1.0/users/me/mailFolders
the beta does a full traversal but you shouldn't be using that in production apps as it subject to change in the future, with the production endpoint at the moment it just does a shallow traversal of whatever folder your searching so you would have to do childFolder traversal https://learn.microsoft.com/en-us/graph/api/mailfolder-list-childfolders?view=graph-rest-1.0&tabs=http of every folder you want to retrieve subfolders for so for in the case of Deleted Items folder you just exclude that.