1. // Provide your implementation for the BSTIndex class here
2. #include "BST.hpp"
3. #include "FileSystem.hpp"
4.  
5. BSTIndex::BSTIndex() : root(nullptr) {}
6.  
7. BSTIndex::~BSTIndex() {
8.     destroyTree(root);
9. }
10.  
11. void BSTIndex::destroyTree(TreeNode* node) {
12.     if (node != nullptr) {
13.         destroyTree(node->left);
14.         destroyTree(node->right);
15.         delete node;
16.     }
17. }
18.  
19. void BSTIndex::CreateIndex(const vector<FileSystemEntry>& Data, const string& IndexType) {
20.     for (int i = 0; i < Data.size(); ++i) {
21.         if (IndexType == "Filename") {
22.             Add(root, i, Data[i].Filename);
23.         } else if (IndexType == "modifiedOn") {
24.             Add(root, i, Data[i].modifiedOn);
25.         } else if (IndexType == "Size") {
26.             Add(root, i, to_string(Data[i].Size));
27.         } else if (IndexType == "Type") {
28.             Add(root, i, Data[i].Type);
29.         } else {
30.             // Handle other index types if needed
31.         }
32.     }
33. }
34.  
35.  
36. void BSTIndex::Add(TreeNode*& node, const int i, const string &Key;) {
37.     insertUtil(node, Key, i);
38. }
39.  
40.  
41. void BSTIndex::insertUtil(TreeNode*& node, const string& key, int idx) {
42.     if (node == nullptr) {
43.         node = new TreeNode(key, idx);
44.     } else if (key < node->key) {
45.         insertUtil(node->left, key, idx);
46.     } else if (key > node->key) {
47.         insertUtil(node->right, key, idx);
48.     } else {
49.         // Key already exists, add index to existing node
50.         node->indices.push_back(idx);
51.     }
52. }
53.  
54. pair<vector<int>, int> BSTIndex::Search(const string& Key, int& nodesVisited) {
55.     nodesVisited = 0; // Initialize the counter for nodes visited
56.     TreeNode* result = searchUtil(root, Key, nodesVisited);
57.     if (result != nullptr) {
58.         return {result->indices, nodesVisited}; // Return indices along with the number of nodes visited
59.     } else {
60.         return {{}, nodesVisited}; // Return empty vector if key not found along with the number of nodes visited
61.     }
62. }
63.  
64. TreeNode* BSTIndex::searchUtil(TreeNode* node, const string& key, int& nodesVisited) {
65.     if (node == nullptr || node->key == key) {
66.         return node;
67.     }
68.     nodesVisited++; // Increment nodes visited for each node traversed
69.     if (key < node->key) {
70.         return searchUtil(node->left, key, nodesVisited);
71.     }
72.     return searchUtil(node->right, key, nodesVisited);
73. }
74.