7.13 LAB: BST validity checker (C++). Please code this in C++. How code I code BSTChecker.h correctly? I've been at a loss for words at what to do. The help would be greatly appreciated. Please show the entire code for BTSChecker.h to know the process behind it.

FILES INCLUDED AND REQUIRED BELOW

_______________________________________________________________________________________________________________________________________

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

_____________________________________________________________________________________________________________________________________________

BSTChecker.h (The file below is the one that needs to be fixed. Do not change the parameter.)

#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

Inispect the class deciaration for a BSI node in Node.h. Access Noden oy cicking 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 CheckBSTValidity0 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 variable 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. 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 . 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 chlld referencing an ancestor, so unit tests are used to test such cases