Complete the function find in BTreeNode.cpp that accepts a BTreeNode * and an in
ID: 3601752 • Letter: C
Question
Complete the function find in BTreeNode.cpp that accepts a BTreeNode * and an int val, and must return the BTreeNode * that contains the matching val, or NULL if val was not found.
## BTreeNode.h##
#ifndef BTREENODE_H
#define BTREENODE_H
#include <string>
#include <algorithm>
#include <vector>
struct BTreeNode {
bool is_leaf_=true;
std::vector<int> elements_;
std::vector<BTreeNode*> children_;
BTreeNode() {}
BTreeNode (std::vector<int> v) {
this->elements_ = v;
}
};
BTreeNode* find(BTreeNode* root, int key);
#endif
## BTreeNode.cpp ##
#include <vector>
#include "BTreeNode.h"
BTreeNode* find(BTreeNode* root, int key) {
// Code Here
int i = 1;
return NULL;
}
Explanation / Answer
function find() in BTreeNode.cpp:
BTreeNode* find(BTreeNode* root, int key)
{
// Find the first element greater than or equal to key
int i = 0;
while (i < n && key > root->elements_[i])
i++;
// If the found element is equal to key, return this node
if (root->elements_[i] == k)
return root;
// If key is not found here and this is a leaf node
if (root->leaf == true)
return NULL;
// Else Go to the appropriate child & search for the key
return find(root->children_[i],key);
}