7.13 LAB: BST validity checker. Please use C++. I need help on coding BTSChecker.h. I have trouble with figuring out how to link the left and right child to the parent/ancestor. The files required are listed below, which are main.cpp, Node.h, BTSChecker.h..

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

#ifndef BSTCHECKER_H #define BSTCHECKER_H

#include "Node.h"

using namespace std;

class BSTChecker { public: static Node* CheckBSTValidity(Node* rootNode) { 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. 8.Unit test 0/1 invalid tree with right child linking to ancestor 9:Unit test Invalid tree with left child linking to parent 10 Unit test Invalid tree with left chid linking to ancestor