Max number of cores in a recursive search tree with Open MP

Question

I want to implement a search tree using a recursive function. In each node, I evaluate a function Pass_or_Die. If Pass then the node is extended into n more branches, otherwise it dies. Suppose a node passes with a certain fixed probability.

Suppose I have available a machine with M > n cores. I would like to use all my cores on the search tree. The code below shows a simple example of a search tree.

My problems with this example using openMP are: 1) The program uses only n cores. So it does not use all the cores available.

2) From the output it seems that the search tree is sieved progressively. This means first all nodes at level 1 are checked, then all nodes at level 2, etc. I would like instead to focus the corse on running through the first nodes and their subtrees until they die or reach the end, then focus on the other nodes.

I am open also for solution using alternatives to openMP.

#include <stdio.h> 
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include "omp.h"

int n = 3;

// Pass with probability prob/100
int Pass_or_Die(int prob)
{
    int max = 100;
    if ((rand()%max)>(max-prob))
        return 1;
    else
        return 0;
}

// extend the node if Pass, kill it if Die. Print current thread in use, current node and PASS or DIE
void extend_node(int base_node, int extension)
{
    // extend the node
    base_node = base_node*10+extension;

    // get thread id number
    int th_id = omp_get_thread_num();

    // just some noise
    sleep(1);

    // if true, then the tree reaches the end, so do not extend
    if (base_node > 100000)
        return;

    // if Pass, then extend the tree. Pass with probability 0.2
    if (Pass_or_Die(20))
    {
        printf("th_id %d - %d PASS\n ", th_id, base_node);
#pragma omp target teams distribute parallel for
        for (int i = 1; i <= n; ++i)
        {
            extend_node(base_node, i);
        }
    }
    else
        printf("th_id %d - %d DIE\n ", th_id, base_node);
    return;
}


int main (int argc, char *argv[]) {

#pragma omp target teams distribute parallel for
    for (int i = 1; i <= n; ++i)
    {
        extend_node(0, i);
    }

    return 0;
}