Need help with two pieces of code and for the implementations use the same method signatures not changing the header, them being "isBST2(t)", and "equalBSTs(t1,t2)". The class bst.py is just a helper class showing which methods are available for use. And the last part are test cases with expected outputs. The code that I need I need help with are labeled Q3 Q4
from google.colab import files bst.py oaded_files = files.upload () import bst Choose Files bst.py - bst.py(text/x-python-script) - 5057 bytes, last modified: 2/21/2023 - 100\% done Saving bst.py to bst (1) -py Write the function is BST2(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 that the root could have. For example, the figure below shows in red the minimum and maximum valid values for every key based on its ancestors. If there is a key that is greater than its maximum valid value or smaller than its minimum valid value, then the tree is not a binary search tree. We can see that all keys in the tree are in their valid ranges, thus the tree is a binary search tree. Valid values for the root are in the range [-infinity, infinity], since it has no ancestors. Since the value at the root is 26 , then its left subtree can only have key values in the [ infinity, 26] range, while the right subtree can only have keys in the [26, in finity] range. If we replaced key 16 by 30 , the tree would no longer be a binary search tree, since 30 is not in the [2,26] range. Notice that we define the ranges based only on a node's ancestors. Valid values for the root are in the range [-infinity, infinity]. Since the value at the root is 26 , then the left subtree can only have key values in the [ in finity, 26] range, while the right subtree can only have keys in the [26, in finity ] range. In general, if the valid key range for a node with key k is [mink,maxk], the resulting valid ranges for its subtress will be [mink,k] for the left subtree and [k,maxk] for the right subtree. 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)
