ERRORS facing:

$$Invalid tree with right child linking to ancestor

Test feedback:

CheckBSTValidity$()$ returned a node that is not the BST rule$-$violating node. The node with either the left or right child pointing to an ancestor must be returned.

$$Invalid tree with left child linking to ancestor

Test feedback:

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

Code:

$$#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;

$\}$

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

return node;

$\}$

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

return node;

$\}$

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

return node;

$\}$

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

return node;

$\}$

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

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

return leftNode;

$\}$

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

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

return rightNode;

$\}$

return nullptr;

$\}$

$\}$;

#endif