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 read the requirement and the failing test and correct the error codes.

Rewrite 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 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

#include "Node.h"

class BSTChecker { public: static Node* CheckBSTValidity(Node* root) { if (root == nullptr) { return nullptr; } if (root->left != nullptr && root->left->key > root->key) { return root->left; } if (root->right != nullptr && root->right->key key) { return root->right; } Node* leftViolator = CheckBSTValidity(root->left); if (leftViolator != nullptr) { return leftViolator; } Node* rightViolator = CheckBSTValidity(root->right); if (rightViolator != nullptr) { return rightViolator; } return nullptr; } };

#endif

3:Compare output Output differs. See highlights below. Input (80, (60, (40, (20, None, (50)), None), None), None) Your output Expected output 50 9:Unit test Invalid tree with left child linking to parent Returned unexpected error code (-11)