An error in a BST implementation may result in a variety of problems. Ex: Key$-$related problems include:

$-$ A node $\backslash ($ X $\backslash )$ in in the left subtree of ancestor $\backslash ($ Y $\backslash )$ with $\backslash ($ X $\backslash )\text{'}$s key $>$ Y$\text{'}$s key

$-$ A node $\backslash ($ X $\backslash )$ in in the right subtree of ancestor $\backslash ($ Y $\backslash )$ with $\backslash ($ X $\backslash )\text{'}$s key $<mtext></mtext><mi>\backslash </mi><mi>(</mi>$ Y $\backslash )\text{'}$s key

Child$-$related problems include:

$-$ A node that is a child of two or more distinct nodes

$-$ A child pointer that points to an ancestor

Examples of key$-$related problems:

Key $\backslash (\backslash$mathbf$\{50\}\backslash )($and $60)$ in $40\text{'}$s left subtree

Examples of child$-$related problems:

Key $66$ in $77\text{'}$s right subtree

$55\text{'}$s left child is an ancestor

BST validity checker overview

This lab requires implementation of a BST validity checker that identifies each type of problem mentioned above. The validity checker can be used to assist with BST implementations.

Determining how to identify key$-$related problems is part of this lab's requirements. As for identifying child$-$related problems, consider a preorder traversal of the two example trees above. A preorder traversal of either encounters the same node more than once. So the two child$-$related problems can be described with a single criterion: A distinct node is visited more than once during preorder traversal.

$-$ Ex: In the left tree, preorder traversal visits node $\backslash (50,25,37,75,88,75\backslash )$ again, and $88$ again.

$-$ Ex: In the right tree, preorder traversal visits node $\backslash (44,22,11,33,55\backslash ),$ and then repeats in an infinite cycle.

So an algorithm to check the validity of BST should stop as soon as any node is visited more than once. Ex: The second visit of $75$ stops traversal in the left tree and the second visit of $44$ stops traversal in the right tree.

Step $1$: Inspect the BSTNode.h file

Inspect the class declaration for a BST node in BSTNode.h$.$ Each node has a key, a left child pointer, and a right child pointer. BSTNode.h is read$-$only, since no changes are required.

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 an argument. If the tree is a valid BST$,$ nullptr must be returned. Otherwise the first$-$encountered problematic node must be returned.

Example figures above show the problematic node in red. Implement a preorder traversal that tracks necessary information, like the valid key range for a node's key and a set of visited nodes. As soon as a violation is encountered, like a node's key being out of range or a node being visited a second time, return that node.

Code in main$()$ creates a variety of trees and runs test cases. Ensure that all tests in main$()$ pass before submitting code for grading.