Can we do better than $O(n\log n)$ building a balanced binary tree?

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 nu

If I understand your question correctly, then yes of course you can build a balanced binary tree in $O(n)$ time. Here is a simple pseudocode:

L = [2, 4, 1, 3, 5, 6, 8]
q = Queue()
node root{value = L[0]}
q.add(root)
k = 1
while !q.isEmpty:
  n = q.pop
  if k < L.size:
     n.left = node{value=L[k]}
     k++
     q.add(n.left)
  if k < L.size:
     n.right = node{value=L[k]}
     k++
     q.add(n.right)

It is not hard to see that this code does run in linear time and builds a balanced binary tree.

What you cannot do, is build a balanced binary search (ordered) tree in $O(n)$ time (using only comparisons on the values). The algorithm above does not guarantee that the value on the root is greater than or equal to every value in the left sub-tree and is less than or equal to every value in the right sub-tree, for every sub-tree.

The algorithm above does not guarantee it and neither does the conc-tree (using appends and prepends). From the wikipedia page, it only guarantees $O(1)$ amortized time for appends and prepends. For inserts, it can only guarantee $O(\log n)$ time.

StackExchange Computer Science Q#65593, answer score: 7