trees figure two isomorphic trees what is the running time of your program (there is linear solution) show that via avl single rotationsany binary search tree can be transformed into another search tree (with the same itemsb give an algorithm to perform this transformation using ( log nrotations on average  show that this transformation can be done with (nrotationsworst-case suppose we want to add the operation findkth to our repertoire the operation findkth(kreturns the kth smallest item in the tree assume all items are distinct explain how to modify the binary search tree to support this operation in (log naverage timewithout sacrificing the time bounds of any other operation since binary search tree with nodes has nullptr pointershalf the space allocated in binary search tree for pointer information is wasted suppose that if node has nullptr left childwe make its left child link to its inorder predecessorand if node has nullptr right childwe make its right child link to its inorder successor this is known as threaded tree and the extra links are called threads how can we distinguish threads from real children pointersb write routines to perform insertion and deletion into tree threaded in the manner described above what is the advantage of using threaded treeswrite program that reads +source code file and outputs list of all identifiers (that isvariable namesbut not keywordsthat are not found in comments or string constantsin alphabetical order each identifier should be output with list of line numbers on which it occurs generate an index for book the input file consists of set of index entries each line consists of the string ix:followed by an index entry name enclosed in bracesfollowed by page number that is enclosed in braces each in an index entry name represents sublevel |represents the start of rangeand |represents the end of the range occasionallythis range will be the same page in that caseoutput only single page number otherwisedo not collapse or expand ranges on your own as an examplefigure shows sample input and figure shows the corresponding output