$7\mathrm{.}11$ LAB: Modified BST validity checker

Step $1$: Inspect the Node.java file

Inspect the class declaration for a BST node in Node.java. Access Node.java by clicking on the orange arrow next to LabProgram.java at the

top of the coding window. Each node has a key, a left child reference, and a right child reference.

Step $2$: Implement the BSTChecker.checkBSTValidity$()$ method

Implement the checkBSTValidity$()$ method in the BSTChecker class in the BSTChecker.java file. The method takes the tree's root node as a

parameter and returns the node that violates BST requirements, or null if the tree is a valid BST$.$ This method must be implemented non$-$

recursively, and it cannot make any calls to recursive methods.

A violating node x will meet one or more of the following conditions:

x is in the left subtree of ancestor Y$,$ but x $\text{'}$s key is $>$Y $\text{'}$s key

x is in the right subtree of ancestor Y$,$ but x $\text{'}$s key is Fx$^(-)\text{'}$s key

X$\text{'}$s left or right child references an ancestor

Note: Other types of BST violations can occur, but are not covered in this lab. For this lab, only check for the violations listed above and not

any others.

The given code in LabProgram.java 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$()$ method is called and the returned node's key, or $"$No violation", is printed.

Fx$^(-)$

If the input is:

$(50,(25,$ None, $(60)),(75))$

which corresponds to the tree above, then the output is:

$60$

because $60$ violates BST requirements by being in the left subtree of $50.$

Ex:which corresponds to the tree above, then the output is:

because $60$ violates BST requirements by being in the left subtree of $50.$

c$^(-)$

If the input is:

$(20,(10),(30,(29),(31)))$

which corresponds to the tree above, then the output is:

No violation

because all BST requirements are met.

The input format doesn't allow creating a tree with a node's child referencing an ancestor, so unit tests are used to test such cases.

Step $3$: Pre$-$order traversal

Somewhere in your code, you must use a pre$-$order traversal to visit all the nodes in the tree. Do so in a natural and meaningful way, e$.$g$.,$ do

a pre$-$order traversal of the tree to check if a child of a node X references an ancestor. Have a comment block preceding the code that does

this in which you must briefly explain why your non$-$recursive code carries out a pre$-$order traversal.

Step $4$: Ensure that every method has at most $30$ lines of code

To satisfy this requirement, you may have to add private helper methods and call them appropriately. However, no methods in this lab can

be recursive. If you do add extra methods, then they must be private. Here is the code what I have right now."import java.util.$*$;

public class BSTChecker $\{$

public static Node checkBSTValidity$($Node rootNode$)\{$

return checkBSTValidity$($rootNode$,$ null, null$)$;

$\}$

private static Node checkBSTValidity$($Node node, Integer min, Integer max$)\{$

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

return null;

$\}$

if $(($min $!=$ null && node.key min$)||($max $!=$ null && node.key $>=$ max$))\{$

return node;

$\}$

Node leftViolation $=$ checkBSTValidity$($node$.$left, min, node.key$)$;

Node rightViolation $=$ checkBSTValidity$($node$.$right, node.key, max$)$;

return $($leftViolation $!=$ null$)?$ leftViolation : rightViolation;

$\}$

public void preOrderTraversal$($Node root$)\{$

if $($root $==$ null$)\{$

return;

$\}$

Stack stack $=$ new Stack;

stack.push$($root$)$;

while $(!$stack.isEmpty$())\{$

Node current $=$ stack.pop$()$;

processNode$($current$)$;

if $($current$.$right $!=$ null$)\{$

stack.push$($current$.$right$)$;

$\}$

if $($current$.$left $!=$ null$)\{$

stack.push$($current$.$left$)$;

$\}$

$\}$

$\}$

private void processNode$($Node node$)\{$

if $($node$.$left $!=$ null && node.left.key $>=$ node.key$)\{$

System.out.println$("$Violation found: Left child of node $"+$ node.key $+"$ references an ancestor."$)$;

$\}$

if $($node$.$right $!=$ null && node.right.key node.key$)\{$

System.out.println$("$Violation found: Right child of node $"+$ node.key $+"$ references an ancestor."$)$;

$\}$

$\}$

$\}$ Can only change the BSTChecker.java file. This is where I don't have a pass$\mathrm{.}8$:Unit test

Invalid tree with right child linking to ancestor

$9$:Unit test

Invalid tree with left child linking to parent

Test feedback

checkBSTValidity$()$ returned a node that is not the BST rule$-$violating no

$$

$10$:Unit test

Invalid tree with left child linking to ancestor Can anyone please help me with these issues based on my code? Please attach the full changed code. Thank you! Also, the other two java file cannot be changed: LabProgram.java, and Node.java