Here is a definition of a function is BST that takes a binary tree and decides if it is a binary search tree.

Function: is BST Inputs: t, a binary tree Preconditions: items in the t must be (pairwise) comparable Output: result, a Boolean Postconditions: result is true if t is a binary search tree, or if for every node in t the left child is either empty or less than the node's root and the right child is either empty or greater than the node's root - and false otherwise

The recursive function is_BST() provided in the file Q3_BST.py implements the is BST function.

# implementation of is BST function def is_BST(t:Tree) -> bool: """ Preconditions: items in the tree must be comparable Postconditions: output is true if t is a binary search tree, false otherwise """ if is_empty(t): return True else: the_root = t.root left_tree = t.left left_root = left_tree.root right_tree = t.right right_root = right_tree.root if left_root == None: left_root_ok = True else: left_root_ok = (left_root < the_root) if right_root == None: right_root_ok = True else: right_root_ok = (right_root > the_root) return (is_BST(left_tree) and is_BST(right_tree) and left_root_ok and right_root_ok)

Write code to construct test trees and complete the test table with six different tests to test this implementation. Add comments to the test table to indicate any edge cases.

Running the test code should produce 'Tests finished'. If any tests fail, try to identify why they failed and add any explanatory comments below the test code.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

%run -i m269_tree %run -i m269_util %run -i Q3_BST

# Write your code to construct test trees here

# Complete the test table BST_tests = [ # case, t, result # Add your tests here, uncomment the tests when you are ready to use them # ('', , ), # ('', , ), # ('', , ), # ('', , ), # ('', , ), # ('', , ) ]

test(is_BST, BST_tests)

# Add any explanatory comments here