[Solved] CS 431 Programming Language Concepts Homework 7

Homework 71 Binary treeThe following questions use the following datatype de nition.datatype data tree =Empty |Node of data tree * data * data tree;1. A full binary tree is one in which every Node has either two Empty childrenor two Node children but not one of each. Write a function isFull of typea tree -> bool that tests whether a tree is full or not. Empty tree isfull.2. Write a function makeBST of typea list -> (a * a -> bool) -> a treethat organizes the items in a list into a binary search tree. The treeneeds not to be balanced and you may assume that no items in the list isrepeated.The 2nd parameter of makeBST is a comparison function that comparestwo items and determine whether the rst one is less than the second oneor not.A binary search tree is either empty or it has two subtrees and a dataitem x, where the items in the left subtree are all smaller than x, theitems in the right subtree are greater than x, and the two subtrees arebinary search tree as well.For example, makeBST [1,3,2] (op <);val it = Node (Node (Empty,1,Empty),2,Node (Empty,3,Empty)) : int treeNote that depending on your implementation, the shape of the tree maylook dierent though it should contain the same elements.13. Write a function searchBST of typea tree -> (a * a -> bool) -> a -> boolthat searches a binary search tree for a given data element and returnstrue if it is found and false otherwise. Your solution should only searchsubtrees that may contain the element you are looking for.If we apply the function in the following way searchBST tree f e, thensearchBST should rst compare e with the tree data d using = to seeif e and d are equal. If they are equal, then return true. Otherwises,searchBST should check if f(e, d) is true or false, if true, then searchthe left subtree and if false, it should search the right subtree.For example, in the following program, the variable isFound should betrue.val t = Node( Node( Empty, 4, Empty ),5,Node( Empty, 6, Empty )); searchBST t (op <) 4;val it = true : boolval t2 = makeBST [3, 6, 2, 1, 4] (op <); searchBST t2 (op <) 2;val it = true : bool searchBST t2 (op <) 5;val it = false : bool2