3a The following keys are added to an empty binary search tree in order: 4,6,23,7,2, -8,46, 36,5. Draw the resulting tree. b You are implementing a binary search tree that allows duplicate keys. In such a tree both the left and the right subtree of a node may contain other nodes with the same key. A tree is composed of node objects that have public fields left, right (subtrees) and key (an integer). The tree has a public field root (the root node). i) Write a procedure Add that adds a new node x to such a binary search tree T. You can use either pseudocode or Java. ii) Describe the (runtime) performance of your Add procedure given inputs with and without duplicate keys. c An application searches English language "texts" (strings) for occurrences of certain "patterns" (also strings) using the Knuth-Morris Pratt algorithm. i) Write out a table containing the Knuth-Morris Pratt at function for the pattern "amanadamanages". ii) How will the input text and input pattern affect the running time? iii) If the same application was used with texts and patterns both composed from the alphabet A = {0,1}, how would this affect your answer to (ii)? How would the input pattern and the input text affect the running time of the application if it used the Boyer-Moore algorithm instead? Compare the English language and the A = {0,1} cases. The three parts carry, respectively. 15%, 40%, and 45% of the marks