We wish to implement a method String insert(char c, String s) that returns a string with c inserted in the correct position in already sorted String s. To do so we will implement insert as follows:

static String insert(char c, String s) {

return insertHelper(c, "", s);

}

static String insertHelper(char c, String left, String right) {} // strip leading characters from right, & append to left 'till insertion point found. Now return left + c + right.

For example, insert('e', "bcdfg") would call

insertHelper('e', "", "bcdfg") which would recursively call

insertHelper('e', "b" , "cdfg") followed by

insertHelper('e', "bc" , "dfg") followed by

insertHelper('e', "bcd", "fg).

This last call would then return "bcd" + 'e' + "fg" which is gives the final result "bcdefg".

IMPLEMENT insertHelper. (Don't implement insert() )

Your implementation of insertHelper must be tailRecursive.