Please solve this question. This is related to recursion and induction. You may use 'base case', 'step case'. Thank you so much!

EExercise 128. Let N be a set of numbers between N and R. Consider the function search: OFBTrees n x N + {0,1} that for an input consisting of a orderedl binary tree t with labels from N and an element n of N gives 1 if n occurs as a label in t, and 0 otherwise. (a) Give a recursive definition of search. We may think of this function as performing a binary search. (b) Write code that implements this function, assuming we have a class OBTree which restricts BTree to ordered binary trees only. (c) Draw a picture of the ordered binary tree tree-3(tree_5(tree 7, tree 4), tree5(tree 3, tree 7)). Imagine you want to add a node with label 4 to the tree. Where should that go? Draw your solution. Do you still have a full binary tree? (d) Write code that takes as inputs an object of the class OBTree and an integer and returns an object of class OBTree in which the second argument has been inserted if it is not already present. Use the previous part to guide you. Hint: Your definition should take advantage of the fact that the tree is ordered and not look at every label. EExercise 128. Let N be a set of numbers between N and R. Consider the function search: OFBTrees n x N + {0,1} that for an input consisting of a orderedl binary tree t with labels from N and an element n of N gives 1 if n occurs as a label in t, and 0 otherwise. (a) Give a recursive definition of search. We may think of this function as performing a binary search. (b) Write code that implements this function, assuming we have a class OBTree which restricts BTree to ordered binary trees only. (c) Draw a picture of the ordered binary tree tree-3(tree_5(tree 7, tree 4), tree5(tree 3, tree 7)). Imagine you want to add a node with label 4 to the tree. Where should that go? Draw your solution. Do you still have a full binary tree? (d) Write code that takes as inputs an object of the class OBTree and an integer and returns an object of class OBTree in which the second argument has been inserted if it is not already present. Use the previous part to guide you. Hint: Your definition should take advantage of the fact that the tree is ordered and not look at every label