data structure (c++)

2 Binary Tree A binary tree is a data structure where all node has at most two children. Excercise: Given the code of the Node struct and the insert method of the tree, implement the binary tree with the following functionalities: Tree: a constructor to initialize a tree object. checkString: returns true if a string is found in a path in the tree starting from the root to any node in the tree. Otherwise, false is returned. charCount: returns the number of a specific character in the whole tree. All cases must be handled. You can define any helper methods as needed. #include using namespace std; struct Node { int ID; char alpha; Node* left; Node* right; Node (int ID, char alpha) { this->ID = ID; this->alpha = alpha; left = NULL; 2 right = NULL; } }; class Tree { public: Tree() { } bool insert(int PID, Node* node) { if (PID == -1) { if (root == NULL) { root = node; return true; } else return false; } return insert (PID, node, root); } bool checkString (string str) { } int charCount (char c) { } checkString: returns true if a string is found in a path in the tree starting fro node in the tree. Otherwise, false is returned. charCount: returns the number of a specific character in the whole tree. All cases must be handled. You can define any helper methods as needed. #include using namespace std; struct Node int ID; char alpha; Node* left; Node* right; Node (int ID, char alpha) { this->ID = ID; this->alpha = alpha; left = NULL; 2 right = NULL; } }; class Tree { public: Tree () { } 3 bool insert(int PID, Node* node) { if (PID == -1) { if (root == NULL) { root = node; return true; } else return false; } return insert (PID, node, root); } bool checkString (string str) { ) int charCount (char c) { } private: Node* root; bool insert(int PID, Node* node, Node*& root) { if (root == NULL) return false; else if (root->ID == PID) { if (root->left == NULL) { root->left = node; return true; } else if (root->right == NULL) { root->right = node; return true; 1 else { return false; } } else return insert(PID, node, root->left) || insert (PID, node, root->right); } return false; } }; int main() { Tree tree; Node* node1 = new Node(1, 'a'); Node* node2 = new Node (2, 'b'); Node* node3 = new Node (3, 'c'); Node* node4 = new Node (4, 'd'); Node* node5 = new Node (5, 'd'); cout