I've recently come across some code for the inorder traversal of a binary search tree which is as follows:

void binary_search_tree::inorder_traversal(bst_node *node, std::function<void(int)> callback) {

    if (node == nullptr) {
        return;
    }

    inorder_traversal(node->left, callback);
    callback(node->value);
    inorder_traversal(node->right, callback);
}

std::vector<int> binary_search_tree::get_elements_inorder() {
    std::vector<int> elements;

    inorder_traversal(root, [&](int node_value) {
        elements.push_back(node_value);
    });

    return elements;
}

From my understanding, the first function recursively traverses the BST inorder, visiting the left, then the node, then the right. The second function then calls this function to add each element to the vector as each node is hit.

My confusion comes from how each value of the node is obtained. Does callback(node->value) store each node value somewhere to be used later? I'm not exactly sure about how this works.

Any help would be much appreciated :) Thank you!

CodePudding user response：

https://en.cppreference.com/w/cpp/utility/functional/function has a pretty good description:

Class template std::function is a general-purpose polymorphic function wrapper. Instances of std::function can store, copy, and invoke any CopyConstructible Callable target -- functions, lambda expressions, bind expressions, or other function objects, as well as pointers to member functions and pointers to data members.

std::function<void(int)> stores a function (or similar) that can be called with an int argument and which returns nothing. In particular you can store a lambda in it.

Here the inorder_traversal function is called with the lambda [&](int node_value) { elements.push_back(node_value); } as argument (under the name callback).

Then later when inorder_traversal calls callback(node->value); it effectively calls the code elements.push_back(node->value). Well not exactly, since this only works because the lambda has captured elements - without that the vector would not be accessible here. But to know more about how that works I suggest that you read up on lambdas - it is a bit beyond the scope of this question.