PYTHON

Write the function bstSort(L) that receives a singly linked list L, sorts L using a binary search tree and returns a sorted version of L. You should insert the items in L to a binary search tree, then traverse the tree to extract its elements into a List object. Items must be inserted and retrieved directly for the List object without using intermediate storage (for example, extracting the items from the List or the binary search tree to a Python list is not allowed).

2. Write the function isBST(t) that receives a binary tree t and determines if t is a binary search tree. For example, your function should return True if it receives the tree on the left and False if it receives the tree on the right (since key 68 is on the left subtree of key 66). Do this by extracting the in-order traversal of the tree to a Python list and checking to see if the list is sorted. Your function must run in time O(n) (no credit will be given if it takes longer than that).

3. Write the function isBST2(t) that receives a binary tree t and determines if t is a binary search tree. Your function should give the same results as the one in the previous question, but now you are not allowed to use extra storage (that is, you cannot extract the elements of the tree to a list). Your function must run in time O(n) (no credit will be given if it takes longer than that). Hint: use recursion; every recursive call should receive the root and the minimum and maximum key values allowed in each sub-tree.

4. Write the function equalBSTs(t1,t2) that receives binary search trees t1 and t2 and determines if they are identical (that is, they have the same keys and the same shape).

5. Write the function extractBSTs(t1,t2) that receives binary search trees t1 and t2 and returns a sorted singly linked list L that contains the combined elements of t1 and t2 sorted in ascending order. For exam- ple, if t1 and t2 are the binary search trees in the image, your function should return the singly linked list L containing [1,2,3,4,5,7,7,8,10,13,14,15,15,16,17,18,24]. Your function must run in time O(n) (no credit will be given if it takes longer than that).

1. Write the function batSort/L) that receives a singly linked list . sorts Luning a bimary search tree and Iturns sorted version of L. You should insert the items in I to a binary match tree, then traverse the tree to extract its elements into a list object. Items must be baserted and retrieved directly for the Lost object without using intermediate storage (for example, extracting the items from the List or the binary march tree to a Python list is not allowed). Compare the running time of this function to the sorting functions you implemented for Lab 2. Write the fiction isBST that receives a binary tree and determines ill is a binary search tree. For example, your function should return True if it receives the tree on the left and False if it receives the tree on the right since my 65 is on the left subtree of lry 66). Do this by extraeting the in order traversal of the tree to a Python list and checking to see if the list issotel. Your function must ran intime On) (no credit will be given if it takes longer than that). 3. Write the function BST2/) that receive a bitary tree and determines iftis a binary search tree. Your function should give the same results as the one in the previous question, but now you are not allowed to se extra storage that is you cannot extract the elements of the tree to a list). Your function mistr in time O(n) (no credit will be given if it talus longer than that). Hit te recursion, every tersive call bould receive the root and the minimum and maximum koy values allowed in each sub-tree. 4. Write the function equalBSTW11.12) that receives binary search trees 'l and 12 and determines if they y are Identical that is, they have the same keys and the same shape). S. Write the function stractBST (t/ce) that receives bitsy search trees and 12 axl returns a sorted singly.linked list that contain the combined elements of th and 12 sorted in ascending order. For exam ple, if I al 2 are the binary search trees in the image your function should return the singly.linked. list L containing 1.2.3.4.5.7.7.8.10,13,14.15, 15, 16, 17, 18, 24). Your Action metri in time On) (no credit will be given if it alors longer than that)