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 CheckBSTValidity() function in the BSTChecker class in the BSTChecker.h file. The function takes the tree's root node as a parameter and returns 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::CheckBSTValidity() function is called and the returned node's key, or "No violation", is printed.

Please help me re-wirte the code BSTChecker in C++

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 << to_string(badNode->key) << endl; } else { cout << "No violation" << endl; } } else { cout << "Failed to parse input tree" << endl; } Node::DeleteTree(userRoot); }

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

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 < (int) str.length()) { // If the character at index i is not whitespace, then return the // substring that starts at i if (!std::isspace(str[i])) { return str.substr(i); } i++; } // Completing the loop means the entire string is whitespace return std::string(); } public: int key; Node* left; Node* right; Node(int nodeKey, Node* leftChild = nullptr, Node* rightChild = nullptr) { key = nodeKey; left = leftChild; right = rightChild; } virtual ~Node() { }

// 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 < currentNode->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 < (int)treeString.length(); i++) { char character = treeString[i]; if ('(' == character) { parenCounter++; } else if (')' == character) { parenCounter--; } else if (',' == character && 0 == parenCounter) { commaIndices.push_back(i); } } // If no commas, treeString is expected to be just the node's key if (0 == commaIndices.size()) { return new Node(std::stoi(treeString)); } // If number of commas is not 2, then the string's format is invalid if (2 != commaIndices.size()) { return nullptr; }

// "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

#include "Node.h"

class BSTChecker { public: static Node *CheckBSTValidity(Node *root) { if (root == nullptr) { return nullptr; // Empty tree is a valid BST } Node *leftChild = root->left; if (leftChild != nullptr) { if (leftChild->key >= root->key) { return leftChild; } Node *leftResult = CheckBSTValidity(leftChild); if (leftResult != nullptr) { return leftResult; } } Node *rightChild = root->right; if (rightChild != nullptr) { if (rightChild->key <= root->key) { return rightChild; } Node *rightResult = CheckBSTValidity(rightChild); if (rightResult != nullptr) { return rightResult; } return nullptr; } };

#endif