Identify trees, lists, and array search costs

Answer all parts concisely and justify time complexities. a) A data model requires each node to have at most two children and a single parent. Name the data structure and describe the typical fields per node. If keys are stored to enable ordered searches, state the average and worst-case time to search by key and what property must hold to achieve the average case. b) You need a structure where each element points to the next element and supports O(1) insertion at the head. Name the structure. Describe how to detect whether it contains a cycle and give the time and space complexity of your method. c) For an unsorted array of n integers, what is the worst-case time complexity to determine whether a target value exists? If the array is sorted, what algorithm would you use and what is the new time complexity? Yes/No: Is binary search valid on an unsorted array? Explain in one sentence.