#ifndef BST$\_$CHECKER$\_$H

#define BST$\_$CHECKER$\_$H

#include "Node.h$"$

class BSTChecker $\{$

public:

static Node$*$ CheckBSTValidity$($Node$*$ root$)\{$

return CheckBSTValidityRecursive$($root$,$ nullptr, nullptr$)$;

$\}$

private:

static Node$*$ CheckBSTValidityRecursive$($Node$*$ node, Node$*$ minNode, Node$*$ maxNode$)\{$

if $($node $==$ nullptr$)\{$

return nullptr;

$\}$

$//$ Check if the node's key violates the BST property

if $(($minNode $!=$ nullptr && node$->$key $<$ minNode$->$key$)||($maxNode $!=$ nullptr && node$->$key $>$ maxNode$->$key$))\{$

return node;

$\}$

$//$ Check if the left child is linking to an ancestor

if $($node$->$left $!=$ nullptr && $($node$->$left $==$ minNode $||$ node$->$left $==$ maxNode$))\{$

return node$->$left;

$\}$

$//$ Check if the right child is linking to an ancestor

if $($node$->$right $!=$ nullptr && $($node$->$right $==$ minNode $||$ node$->$right $==$ maxNode$))\{$

return node$->$right;

$\}$

$//$ Recursively check the left subtree

Node$*$ leftViolation $=$ CheckBSTValidityRecursive$($node$->$left, minNode, node$)$;

if $($leftViolation $!=$ nullptr$)\{$

return leftViolation;

$\}$

$//$ Recursively check the right subtree

Node$*$ rightViolation $=$ CheckBSTValidityRecursive$($node$->$right, node, maxNode$)$;

if $($rightViolation $!=$ nullptr$)\{$

return rightViolation;

$\}$

$//$ If no violations are found, return nullptr

return nullptr;

$\}$

static bool IsDescendant$($Node$*$ ancestor, Node$*$ node$)\{$

if $(!$ancestor $||!$node$)\{$

return false;

$\}$

if $($ancestor $==$ node$)\{$

return true;

$\}$

return IsDescendant$($ancestor$->$left, node$)||$ IsDescendant$($ancestor$->$right, node$)$;

$\}$

$\}$;

#endif

Cant seem to pass the last two tests being

$9$:Unit test

$0/3$

Invalid tree with left child linking to parent

Test feedback

CheckBSTValidity$()$ returned a node that is not the BST rule$-$violating node.

$10$:Unit test

$0/3$

Invalid tree with left child linking to ancestor

Test feedback

CheckBSTValidity$()$ returned a node that is not the BST rule$-$violating node.

Here are the read only main and node.h files

#include

#include

#include "Node.h$"$

#include "BSTChecker.h$"$

using namespace std;

int main$()\{$

Node$*$ badNode;

Node$*$ userRoot;

string inputString;

inputString $="(10,(20),(30,(29),(31)))"$;

userRoot $=$ Node::Parse$($inputString$)$;

if $($userRoot$)\{$

badNode $=$ BSTChecker::CheckBSTValidity$($userRoot$)$;

cout $<<$ "Output should be: $20"<<$ endl;

if $($badNode$)\{$

cout $<<$ to$\_$string$($badNode$->$key$)<<$ endl;

$\}$

else $\{$

cout $<<"$No violation" $<<$ endl;

$\}$

$\}$

else $\{$

cout $<<$ "Failed to parse input tree" $<<$ endl;

$\}$

Node::DeleteTree$($userRoot$)$;

inputString $="(20,(10),(30,(29),(31)))"$;

userRoot $=$ Node::Parse$($inputString$)$;

if $($userRoot$)\{$

badNode $=$ BSTChecker::CheckBSTValidity$($userRoot$)$;

cout $<<$ "Output should be: No violation" $<<$ endl;

if $($badNode$)\{$

cout $<<$ to$\_$string$($badNode$->$key$)<<$ endl;

$\}$

else $\{$

cout $<<"$No violation" $<<$ endl;

$\}$

$\}$

else $\{$

cout $<<$ "Failed to parse input tree" $<<$ endl;

$\}$

Node::DeleteTree$($userRoot$)$;

inputString $="(80,(60,(40,(20,$ None, $(50)),$ None$),$ None$),$ None$)"$;

userRoot $=$ Node::Parse$($inputString$)$;

if $($userRoot$)\{$

badNode $=$ BSTChecker::CheckBSTValidity$($userRoot$)$;

cout $<<$ "Output should be: $50"<<$ endl;

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$*$ root $=$ new Node$(68)$;

root$->$InsertAll$(\{77,75,73,71,76,54,19,91,12\})$;

Node$*$ userResult $=$ BSTChecker::CheckBSTValidity$($root$)$;

$//$ Check the user's result

if $($nullptr $==$ userResult$)\{$

cout $<<$ "BSTChecker::CheckBSTValidity$()$ correctly returned nullptr" $<<$ endl;

$\}$

else $\{$

cout $<<$ "BSTChecker::CheckBSTValidity$()$ returned something other than nullptr $"$;

cout $<<$ "for a valid BST$.$ Expected return value is nullptr." $<<$ endl;

$\}$

Node::DeleteTree$($root$)$;

Node$*$ node$22=$ new Node$(22,$ new Node$(11),$ new Node$(33))$;

badNode $=$ new Node$(40,$ nullptr, new Node$(50))$;

root $=$ new Node$(44,$ node$22,$ badNode$)$;

$//$ Call the user's CheckBSTValidity$()$ function

userResult $=$ BSTChecker::CheckBSTValidity$($root$)$;

$//$ Check the user's result

bool pass $=$ false;

if $($badNode $==$ userResult$)\{$

cout $<<$ "CheckBSTValidity$()$ correctly returned the rule$-$violating node." $<<$ endl;

pass $=$ true;

$\}$

node.h file