Please help on 7.13 LAB: BST validity checker. I've been struggling with figuring out how to code BTSChecker.h. I would really appreciate the help. Must be coded in C++. Only the files shown below are to be used.

TESTS FOR THE CODE

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

main.cpp

#include #include #include "Node.h" #include "BSTChecker.h" using namespace std;

int main(int argc, char *argv[]) { // Get user input string userInput; getline(cin, userInput); // Parse into a binary ree Node* userRoot = Node::Parse(userInput); if (userRoot) { Node* badNode = BSTChecker::CheckBSTValidity(userRoot); if (badNode) { cout key)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Node.h

#ifndef NODE_H #define NODE_H

#include #include #include

class Node { private: static std::string RemoveLeadingWhitespace(std::string str) { int i = 0; while (i

// Counts the number of nodes in this tree virtual int Count() { int leftCount = 0; if (left) { leftCount = left->Count(); } int rightCount = 0; if (right) { rightCount = right->Count(); } return 1 + leftCount + rightCount; } static void DeleteTree(Node* root) { if (root) { DeleteTree(root->left); DeleteTree(root->right); delete root; } } // Inserts the new node into the tree. virtual void Insert(Node* node) { Node* currentNode = this; while (currentNode) { if (node->key key) { if (currentNode->left) { currentNode = currentNode->left; } else { currentNode->left = node; currentNode = nullptr; } } else { if (currentNode->right) { currentNode = currentNode->right; } else { currentNode->right = node; currentNode = nullptr; } } } } virtual void InsertAll(const std::vector& keys) { for (int key : keys) { Insert(new Node(key)); } } static Node* Parse(std::string treeString) { // # A node is enclosed in parentheses with a either just a key: (key), // or a key, left child, and right child triplet: (key, left, right). The // left and right children, if present, can be either a nested node or // "null". // Remove leading whitespace first treeString = Node::RemoveLeadingWhitespace(treeString); // The string must be non-empty, start with "(", and end with ")" if (0 == treeString.length() || treeString[0] != '(' || treeString[treeString.length() - 1] != ')') { return nullptr; } // Parse between parentheses treeString = treeString.substr(1, treeString.length() - 2); // Find non-nested commas std::vector commaIndices; int parenCounter = 0; for (int i = 0 ; i

// "Split" on comma int i1 = commaIndices[0]; int i2 = commaIndices[1]; std::string piece1 = treeString.substr(0, i1); std::string piece2 = treeString.substr(i1 + 1, i2 - i1 - 1); std::string piece3 = treeString.substr(i2 + 1);

// Make the node with just the key Node* nodeToReturn = new Node(stoi(piece1)); // Recursively parse children nodeToReturn->left = Node::Parse(piece2); nodeToReturn->right = Node::Parse(piece3); return nodeToReturn; } };

#endif

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

BTSChecker.h (Code that must be corrected)

#ifndef BSTCHECKER_H #define BSTCHECKER_H

// Your code here (include additional header files, if needed) #include "Node.h"

class BSTChecker { public: static Node* CheckBSTValidity(Node* rootNode) { // Your code here (remove the placeholder line below) return rootNode; } };

#endif

7.13 LAB: BST validity checker Step 1: Inspect the Node.h file Inspect the class declaration for a BST node in Node.h. Access Node.h by clicking on the orange arrow next to main.cpp at the top of the coding window. Each node has a key, a left child pointer, and a right child pointer. Step 2: Implement the BSTChecker::CheckBSTValidity() function Implement the CheckBSTValidityO function in the BSTChecker class in the BSTChecker.h file, The function takes the tree's root node as a parameter and retums the node that violates BST requirements, or nullptr if the tree is a valid BST. A violating node will be one of three things: - A node in the left subtree of an ancestor with a lesser key - A node in the right subtree of an ancestor with a greater key - A node with the left or right member varlable pointing to an ancestor The given code in main.cpp reads and parses input, and builds the tree for you. Nodes are presented in the form (key, leftchild, rightchild), where leftChild and rightChild can be nested nodes or "None". A leaf node is of the form (key). After parsing tree input, the BSTChecker: CheckBSTValidity0 function is called and the returned node's key; or "No violation", is printed. Ex: If the input is: (50,(25,None,(60)),(75)) which corresponds to the tree above, then the output is: 60 because 60 violates BST requirements by being in the left subtree of 50 . EX: If the input is: (20,(10),(30,(29),(31)) which corresponds to the tree above, then the output is: No violation because all BST requirements are met. The input format doesnt allow creating a tree with a node's child referencing an ancestor; so unit tests are used to test such cases. Latest submission - Total score: 5/10 Only show failing tests 1.Compare outout A Input Your output 3:Compare output A 0/1 Output differs. See highlights below. Special aharacter legend Input (80,(60,(40,(20, None, (50)), None), None), None ) Your output Expected output 50 4Unit test x Valid tree with 10 nodes Test feedback 5.Unit test Invalid tree with right child's key less than parent's key Test feedback 6. Unit test Invalid tree with left child's key greater than parent's key Test feedback 7:Unit test Invalid tree with lesser key in right subtree Test feedback 8.Unit test Invalid tree with right child linking to ancestor Test feedback 9.Unit test Invalid tree with left child linking to parent I 10:Unit test Invalid tree with left child linking to ancestor