I'm (foolishly it turns out) confident that the answer to this question is no. So why am I asking?
Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-structure for which he asserts various properties. If these properties hold then it seems to me that it must be possible to build a balanced binary tree in better than $O(n\log n)$ time.
I don't believe this so I'm wondering where the flaw is in my thinking.
The data-structure is the conc-tree list. In it's standard form it looks like a normal binary tree and comes with a
concat operation that ensures the invariant that the left and right subtrees of any node never differ in height by more than one. As expected
concat has complexity $O(\log n)$.
But there's a builder variant of the conc-tree list called the
Append list. This variant allows for temporary height differences in subtrees of more than one. Amortized $O(1)$ time appends are claimed for this variant.
So it seems appending $n$ elements must have a complexity of $O(n)$.
However it's a characteristic of this variant that whenever $n$ is a power of two one ends up with a complete balanced binary tree (containing all elements inserted so far). So while temporary imbalances are allowed the tree becomes balanced every power of 2 insertions.
In this variant a new class of nodes, called
Append nodes, are introduced and it's these nodes whose subtrees are allowed differ in height by more than one. However every $2^k$ insertions all such temporary nodes are eliminated.
The Wikipedia page page describes the algorithm fairly succinctly (see the description of the basic data-structure and the
append method in particular).
So when $n$ is a power of two our cost for inserting elements is $O(n)$ and we've built a balanced binary tree. Or so it seems.
In a separate question I effectively asked "if I can state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, is this enough to allow me to state the complexity for all values of $n$?"
I can see from Yuval Filmus's answer that the answer is no, but that "in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold."
So it seems to me that in this case if inserting $n$ elements has complexity $O(n)$ and every $2^k$ elements I have a balanced binary tree then the cost of building balanced binary trees with this conc-tree variant approach must be $O(n)$.
So what's wrong here? To be honest I can't see the amortized $O(1)$ append time claimed for this variant. I can see that often insertions do have cost $O(1)$ but that when one looks at what's happening with the temporary
Append nodes the overall insertion cost looks to me to be amortized $O(\log n)$.
If this is the case then building our balanced binary tree has an unsurprising $O(n\log n)$ cost.
Sorry for such a long question and sorry for not going into detail about the algorithm in question - instead leaving you to look around on Wikipedia.