# Creating Tasks with parallel_invoke

Suppose you want to search a binary tree for the node that contains a specific value. Here is sequential code to do this:

Nodes are represented by `struct TreeNode`:

    struct TreeNode {
        int value;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;

        ~TreeNode() {
            delete left;
            delete right;
        }
    };

The function `serial_tree_search` is a recursive algorithm that checks the current node and, if the value is not found, calls itself on the left and right subtree.

    void serial_tree_search(TreeNode* node, int target, TreeNode*& result) {
        if (node && !result) {
            if (node->value == target) {
                result = node;
            } else {
                serial_tree_search(node->left, target, result);
                serial_tree_search(node->right, target, result);
            }
        }
    }

To improve performance, you can use `oneapi::tbb::parallel_invoke` to search the tree in parallel:

A recursive base case is used after a minimum size threshold is reached to avoid parallel overheads. Since more than one thread can call the base case concurrently as part of the same tree, `result` is held in an atomic variable.

    void sequential_tree_search(TreeNode* node, int target, std::atomic<TreeNode*>& result) {
        if (node && !result.load()) {
            if (node->value == target) {
                result.store(node); // overwrite is ok since any result is valid
            } else {
                sequential_tree_search(node->left, target, result);
                sequential_tree_search(node->right, target, result);
            }
        }
    }

The function `oneapi::tbb::parallel_invoke` runs multiple independent tasks in parallel. Here is a function `parallel_invoke_search`, where two lambdas are passed that define tasks that search the left and right subtrees of the current node in parallel:

    void parallel_invoke_search(TreeNode* node, int target, std::atomic<TreeNode*>& result,
                                size_t depth_threshold = initial_depth_threshold) {
        if (node && !result.load()) {
            if (node->value == target) {
                result.store(node); // overwrite is ok since any result is valid
            } else if (depth_threshold == 0) {
                sequential_tree_search(node, target, result);
            } else {
                tbb::parallel_invoke(
                    [&] { parallel_invoke_search(node->left, target, result, depth_threshold - 1);  },
                    [&] { parallel_invoke_search(node->right, target, result, depth_threshold - 1); }
                );
            }
        }
    }

If the value is found, the pointer to the node that contains the value is stored in the `std::atomic<TreeNode*> result`. This example uses recursion to create many tasks, instead of just two. The depth of the parallel recursion is limited by the `depth_threshold` parameter. After this depth is reached, the search falls back to a sequential approach. The value of `result` is periodically checked to see if the value has been found by other concurrent tasks, and if so, the search in the current task is terminated. Because multiple threads may access `result` concurrently, an atomic variable is used, even from the sequential base case.

Because `oneapi::tbb::parallel_invoke` is a fork-join algorithm, each level of the recursion does not complete until both the left and right subtrees have completed.