You may be able to guarantee it in this particular case with region-based allocation (also called arena allocation); discarding a region, or resetting its allocation pointer back to the beginning, is a constant-time operation. If your very large tree is in a single region, and it's the only thing in that region, then you can reclaim the entire thing in constant time as soon as you no longer need it.
Region-based memory management is commonly used, for example, with per-frame heaps in games, or per-request heaps in servers; but in those cases memory is not reclaimed immediately. The MLKit implements Standard ML with regions instead of garbage collection, though recent versions also have GC.
That only works if you are able to prove none of your objects do anything in their destructors.
In practice, manually memory managed languages always conflate memory and other resources. A File object is not just a block of memory, it's also a file descriptor, etc. So you have to run the destructors at the 'right' times and can't just toss the memory. In special cases where you control every allocation, sure, but often that isn't practical.
It's true that this solution doesn't apply when you have finalizers, but I think of that as the unusual case, not the usual one. I don't understand what you mean by "special cases where you control every allocation"; how are things getting allocated in your arena without you controlling them? Who is "you" if not the author of the program, who controls everything in it?
Libraries. If your libraries can't do that because you wrote your own malloc to get this arena allocation, it's because your strategy isn't general and will break the moment you want to use libraries that allocate.
The malloc interface doesn't support finalizers anyway! If a library is using malloc, but needs finalizers, it's going to have to invoke its own finalizers manually, usually just before it manually invokes free().
Also, though, it's very unusual to install an arena allocator as a replacement for malloc and (as a no-op) free — malloc has no way to specify which of possibly several arenas you want to allocate in, arena allocators suck at realloc, and writing an arena allocator that invokes malloc to get its arena is significantly easier than writing one that uses a variety of platform-specific calls depending on compilation options. Instead, you write your own arena allocation functions (h_alloc or apr_palloc or whatever), and then you invoke them explicitly, in your own code. Non-arena-aware library code will just keep invoking malloc as usual.
The case where you might end up with library code invoking your arena allocator is where you supply your allocator as an argument to something — like C++ STL containers or, again, APR pools, for example with apr_pool_create_ex. But that still doesn't mean you have to depend on the allocator to invoke finalizers — after all, the standard library operator new and operator delete don't invoke finalizers, instead relying on other finalizers (destructors) to invoke finalizers and then invoke operator free. That still works — your files still get closed — even if the "operator free" is a nop because you're allocating out of an arena. In that case you don't get the major benefit of arena allocation (fast constant-time reclamation of the whole arena), just the minor ones, no fragmentation and fast constant-time allocation.
A more useful strategy is often to attach your finalizers to the arena instead of allocations within it; in the case of apr_palloc you can do this by creating subpools with apr_pool_create and attaching cleanup functions to them with apr_pool_userdata_set.
Regardless, my claim was more restricted than the one you're arguing against. I claimed that arena allocation can guarantee both that there are no pauses and that memory is reclaimed immediately in this case, where you have an arbirarily large tree of objects that dies at a single point in time, and in many similar cases. This is what wgd was claiming was impossible in their second claim: "For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later." That claim is not true.
As far as I know, however, wgd's first and less general claim is true: there's no way to extend this region-based strategy even to the general case of immediate memory reclamation without losing the constant-time guarantee, much less the even more general case of immediate execution of arbitrary finalizers. (By contrast, reference counting can guarantee immediate memory reclamation and immediate execution of arbitrary finalizers, although at the cost of unbounded pauses, and not in the general case because it can't handle cycles.) Obviously you can't execute an unbounded number of finalizers in constant or even bounded time, or call close() on an unbounded number of file descriptors in constant or even bounded time.
But that doesn't mean you can't reclaim an unbounded number of memory allocations in constant time. You can, it's a useful thing to do, and people do it all the time. If you've fetched an URL from Apache today you've done it yourself, even if you didn't know it.
Region-based memory management is commonly used, for example, with per-frame heaps in games, or per-request heaps in servers; but in those cases memory is not reclaimed immediately. The MLKit implements Standard ML with regions instead of garbage collection, though recent versions also have GC.