BST Implementation errors

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

A node $x$ in in the left subtree of ancestor $Y$ with $x\text{'}$s key $>Y\text{'}$s key

A node $x$ in in the right subtree of ancestor $Y$ with $x\text{'}$s key $5050,25,37,75,88,7544,22,11,33,55>\text{'}s$ key

Child$-$related problems include:

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

A child pointer that points $toan$ ancestor

Examples $of$ key$-$relater nrnhleme

Key $50(and60)in40\text{'}s$ left subtree

Key $66in77\text{'}s$ right subtree

Examples $of$ child$-$related problems:

Node $75is$ a child $of$ two distinct

nodes

$55\text{'}s$ left child $isan$ 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 $50,25,37,75,88,75$ again, and $88$ again.

$Ex$: $In$ the right tree, preorder traversal visits node $44,22,11,33,55,$ and then repeats $inan$ infinite cycle

$Soan$ algorithm $to$ check the validity $ofBST$ should stop $as$ soon $as$ any node $is$ visited more than once. $Ex$: The second visit $of75$ stops traversal $in$ the left tree and the second visit $of44$ 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.$his$ 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 $asan$ 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.

$>$ Run

main.$cpp(read-$only$)$

$(7)$ History

Tutorial