Java Spring tree structure @async

Question

For a project I am working on I have created a tree structure. Every node in the tree represents a "task" that can be executed and takes an unknown amount of time. Examples of these "tasks" include but are not limited to: running commands, making HTTP requests or interacting with a database.

As the code must be ran as efficiently as possible, these tasks can be wrapped in a function annotated with @Async so they can run in parallel. Once a node finishes running, all child nodes are also executed using the same @Async wrapper. This cycle continues until the entire tree has finished, either successfully or with failed branches.

However, the problem is that the main thread should wait until the ENTIRE tree is done doing it's thing before continuing. I have tried putting all CompletableFuture results into a list and then checking whether all are completed, but this is problematic because a node must finish before triggering it's children.

Another way in which I have managed to hack it together is to have a set of nodes which keeps track of all nodes which are currently running/queued. Once the list is empty, and therefore all nodes are done, the thread calls a callback function which triggers the main branch of code again to continue. However, the problem with this is that the main branch will continue to be executed on one of the "worker" threads. It also utilizes a callback whereas ideally the caller function would not know that the function being executed is asynchronous; all it needs to do is call it.

Tldr: How can I make a main thread wait until an entire tree has finished running asynchronously.

EDIT 1 September 2021: I may not have described the problem as accurately as may be needed. I want to clarify that I want to asynchronously VISIT every node in the tree. I am not looking for a specific node so it's not a searching problem.

Below I have included an animation of how this could work. All the nodes that are displayed as "working" are being executed on a separate thread. Only once every node is completed, and the entire tree is green, I want the main thread to continue on it's way.

Answer 1

So following up on this, I managed to solve it in the following way:

I start the first "root" task on the main thread, after which I lock the thread by making it wait for a CompletableFuture. The different worker threads then go their own way. Once a task has finished, it will trigger it's child tasks on their own respective worker thread.

In parallel, a stack structure is used to keep track of the different tasks currently in progress. Every time a task finishes it removes itself from the call stack and checks if it's now empty. If it is empty, that means all worker threads have finished, and the CompletableFuture is called, releasing the threadlock.