Step $1$: Inspect the Node.py file

Inspect the class declaration for a BST node in Node.py$.$ Access Node.py by clicking on the orange arrow next to main.py 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 check$\_$bst$\_$validity$()$ function

Implement the check$\_$bst$\_$validity$()$ function in the BSTChecker.py file. The function takes the tree's root node as a parameter and returns the node that violates BST requirements, or None if the tree is a valid BST$.$

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 $<$ Y$\text{'}$s key

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

Note: Other types of BST violations can occur, but are not covered in this lab.

The given code in main.py reads and parses input, and builds the tree for you. Nodes are presented in the form $($key$,$ left$\_$child, right$\_$child$),$ where left$\_$child and right$\_$child can be nested nodes or None. A leaf node is of the form $($key$).$ After parsing tree input, the check$\_$bst$\_$validity$()$ function is called and the returned node's key $($or "None"$)$ is printed.

# Returns None if root$\_$node is the root of a valid BST$.$

# If a BST violation occurs, the node causing the violation is returned. Such a

# node may be one of three things:

# $1.$ A node in the left subtree of an ancestor with a lesser key

# $2.$ A node in the right subtree of an ancestor with a greater key

# $3.$ A node with the left or right attribute referencing an ancestor

def check$\_$bst$\_$validity$($root$\_$node$)$:

# Your code here

return root$\_$node

from Node import Node

from BSTChecker import check$\_$bst$\_$validity

# Get user input and parse into a binary tree

user$\_$input $=$ input$()$

user$\_$root $=$ Node.parse$($user$\_$input$)$

if user$\_$root $==$ None:

print$("$Failed to parse input tree"$)$

else:

bad$\_$node $=$ check$\_$bst$\_$validity$($user$\_$root$)$

if bad$\_$node $!=$ None:

print$($str$($bad$\_$node.key$))$

else:

print$("$None$")$

class Node:

def $\_\_$init$\_\_($self$,$ key, left$=$None, right$=$None$)$:

self.key $=$ key

self.left $=$ left

self.right $=$ right

# Counts the number of nodes in this tree

def count$($self$)$:

left$\_$count $=0$

if self.left $!=$ None:

left$\_$count $=$ self.left.count$()$

right$\_$count $=0$

if self.right $!=$ None:

right$\_$count $=$ self.right.count$()$

return $1+$ left$\_$count $+$ right$\_$count

# Inserts the new node into the tree.

def insert$($self$,$ node$)$:

current$\_$node $=$ self

while current$\_$node is not None:

if node.key $<$ current$\_$node.key:

# If there is no left child, add the new

# node here; otherwise repeat from the

# left child.

if current$\_$node.left is None:

current$\_$node.left $=$ node

current$\_$node $=$ None

else:

current$\_$node $=$ current$\_$node.left

else:

# If there is no right child, add the new

# node here; otherwise repeat from the

# right child.

if current$\_$node.right is None:

current$\_$node.right $=$ node

current$\_$node $=$ None

else:

current$\_$node $=$ current$\_$node.right

def insert$\_$all$($self$,$ keys$)$:

for key in keys:

self.insert$($Node$($key$))$

@staticmethod

def parse$($tree$\_$str$)$:

# A node is enclosed in parentheses with a either just a key: $($key$),$ or

# a key, left child, and right child triplet: $($key$,$ left, right$).$ The

# left and right children, if present, can be either a nested node or

# "None".

#

# Remove whitespace on ends first

tree$\_$str $=$ tree$\_$str$.$strip$()$

#

# The string must be non$-$empty, start with $"(",$ and end with $")"$

if tree$\_$str $==""$ or tree$\_$str$[0]!="("$ or tree$\_$str$[-1]!=")"$:

return None

# Parse between parentheses

tree$\_$str $=$ tree$\_$str$[1$:$-1]$

# Find non$-$nested commas

comma$\_$indices $=[]$

paren$\_$counter $=0$

for i in range$($len$($tree$\_$str$))$:

character $=$ tree$\_$str$[$i$]$

if character $==\text{'}(\text{'}$:

paren$\_$counter $+=1$

elif character $==\text{'})\text{'}$:

paren$\_$counter $-=1$

elif character $==\text{'},\text{'}$ and paren$\_$counter $==0$:

comma$\_$indices.append$($i$)$

# If no commas, tree$\_$str is expected to be just the node's key

if len$($comma$\_$indices$)==0$:

return Node$($int$($tree$\_$str$))$

# If number of commas is not $2,$ then the string's format is invalid

if len$($comma$\_$indices$)!=2$:

return None

# "Split" on comma

i$1=$ comma$\_$indices$[0]$

i$2=$ comma$\_$indices$[1]$

pieces $=[$tree$\_$str$[0$:i$1],$ tree$\_$str$[$i$1+1$:i$2],$