A). If we see the first basic approach , then we can find the middle element in O(n) .
We are using here top - down approach i.e , Recursively designing BST from root to leaves .
List middle element can be found in O(n) which is the root .
Then, similarly , left subtree and right subtree mid element (root) can be found in O(n) time .
root cost = n
Left + right subtree cost = 2n
Total cost = n + 2n + 4n + 8n + .......... = O(n)
and the height is O(h) = O(log n)
Hence, total complexity ==> O(n logn) .
Now, we use 2nd approach , which can reduce this complexity to O(n) .
Apply both top down and bottom up approach,
First finding middle element takes O(n) time .
Now, traverse along first element to root which has n/2 elements in the path as the tree is balanced , which takes O(n). This follows bottom up approach .
And, similarly, making root element as head pointer , make a BST (right subtree ) just by traversing the elements. This follows top down approach .
Hence , total time ==> O(n + n + n) = O(n) . This includes finding the mid element and traversing from leaf to root and then traverse from root to leaf .
B). Simple procedure , access all the elements in O(n) .