Before trying out the above code, it is always best to sit down with a paper and pen and conduct a dry run of the code a few times to see how it works.

Complexity of the Algorithm

The previous code has a complexity of O(N), where N is the number of nodes in the tree.

Inorder traversal requires O(N) time. As we are accessing each element of the array exactly once. After that, we are calculating the median value of the array, breaking it into two halves, and again calculating the median. This will take O(logN) time. Finally, the build method also has a time complexity of O(N).

So the total time complexity would be O(N+logN+N) ~ O(N).

We are creating an array of size N. And then again creating a binary tree of size N. And also, keep in mind that this is a recursive call that is called twice with half the data of the first call. So it will take a memory of O(logN).

So the total memory complexity would be O(N+N+logN) ~ O(N) as well.