Help me out with this question along with the explanation.

Problem 1. Let A be an array holding n distinct integer values. We say a tree T is a pre-order realization of A if T holds the values in A and a pre-order traversal of T visits the values in the order they appear in A. Your task is to design an algorithm for testing if there exists a pre-order realiza tion T of a given array A such that the in-order traversal of T visits the values of A in sorted order. And if such realization exists to create it and return it. For example, the array (2,3,1,4) does not have a realization, but the following examples do: (a) A = (2,1, 3, 4) (b) A (21,4,3) Remember to: a) describe your algorithm in plain English, b) prove it correctness, and c) analyze its time complexity. To get full marks, your algorithm should get run is O(n2) time