Lol, I like how no one is talking about DSW in the replies to the comment about DSW. > [F]ind middle, use it as root, recursively build two subtrees. That's n

Lol, I like how no one is talking about DSW in the replies to the comment about DSW. > [F]ind middle, use it as root, recursively build two subtrees. That's not DSW. DSW should be way more efficient. > With a singly-linked list, it's much harder; I don't know [...] if a more efficient [...] algorithm exists. This is DSW. DSW starts with a sorted linked list--called a "vine"--and builds the tree from that, in place. The vine is a singly linked list in the sense that you only need the successor pointer (though each node obviously needs space for a predecessor pointer since it's being turned into a tree). The algorithm is O(n) time and O(1) space and is actually very elegant. Essentially, you treat the list as a completely unbalanced tree skewed to the right. Then you repeatedly apply a `compress` routine that scans down the far right path in the tree to balance it. From Wikipedia routine vine-to-tree(root, size) leaves ← size + 1 − 2^⌊log2(size + 1))⌋ compress(root, leaves) size ← size − leaves while size > 1 compress(root, ⌊size / 2⌋) size ← ⌊size / 2⌋ routine compress(root, count) scanner ← root for i ← 1 to count child ← scanner.right scanner.right ← child.right scanner ← scanner.right child.right ← scanner.left scanner.left ← child Both the naive algorithm and DSW are O(n), but the naive algorithm has a time complexity of about 2n while DSW has a time complexity of about 0.63n, assuming we start with a vine.