USE PROLOG Write a file name 'bstStuff. pl' For all of the below, we'll represent a Binary Search Tree in prolog the following way:
bst(L, V, R)
.. where:
we presume 'V' is a number
'L' is a 'bst' holding elements strictly less than 'V', or is empty
'R' is a 'bst' holding elements greater than or equal to 'V', or is empty
'nil' represents an empty node/subtree
e. g.:
a very small bst holding only '1' is:
bst(nil, 1, nil).
a balanced bst holding '1' through '3' is:
bst( bst(nil, 1, nil), 2, bst(nil, 3, nil)).
an imbalanced bst holding '1' through '3' is:
bst( bst( bst( nil, 1, nil), 2, nil), 3, nil).
'bstStuff. pl' should contain three definitions:
get_min(bst(L, V, R), X) where 'X' is the minimal element in the bst given. You need no more than two rules to define it, but you can use as many as you like.
get_max(A, X) where 'X' is the maximal element in the bst given. You need no more than two rules to define it, but you can use as many as you like.
is_bst(bst(L, V, R)) where the bst is tested to see if it is a correctly-formed bst. You need no more than one rule to define it, but you can use as many as you like. While using only one rule might feel a bit complex, it will make the definition much cleaner and easier to debug. Hint: think about what it means for a tree to be a bst and take a look at get_min and get_max.