# Build a balanced binary tree from list in linear time

I couldn't figure this one out. Given an unsorted list, we want to build a balanced binary tree (not a search tree, namely - left child is of lower key, and right child of higher key). Can we do it in linear time? Thanks!

• What do you think? What have you tried? Please edit the question to show your thoughts, partial progress or where you got stuck. – John L. Mar 5 '19 at 13:05
• Are you over there? – John L. Mar 6 '19 at 14:27
• I thought maybe building a heap out of the list in O(n), and then start to switch nodes between parent nodes and it's children accordingly until we get a balanced binary tree, but i think this "solution" misses a lot of small points. – Yariv Levy Mar 7 '19 at 9:50
• If this is not a search tree, and you just need a balanced binary tree then this is rather simple. Assume $n = 2^k - 1$ w.l.o.g., then have element $A[i]$ be the left child of $A[\lfloor i / 2 \rfloor ]$ if $i$ is even, otherwise it is the right child if $i$ is odd. If you want an ordered tree, things become more difficult. This assumes $A$ is 1-indexed. – ryan Mar 19 '19 at 21:45
• @ryan Thanks, but it's not what I meant. I wanted a binary tree (namely - left child smaller and right child bigger), which is not necessarily a BST. – Yariv Levy Mar 19 '19 at 21:47

An alternative approach (arguably more elegant). This basically does the same operations as my other answer, just in a different order. It is as follows:

build-tree(list A of length n):
if n == 1:
return singleton tree of the 1 element in A.

let m be the median element of A  # linear time select

let L be all elements in A less than m
let R be all elements in A greater than m

construct a max-heap HL from L in linear time
construct a min-heap HR from R in linear time

let m be the root node of tree T
let the structure of HL be the structure of all  left-children in T
let the structure of HR be the structure of all right-children in T

return T


Let's try an example on $$[8,12,9,15,5,1,10,3,11,14,2,4,13,7,6]$$.

1. First we find the median $$m = 8$$.
2. We find $$L = [5,1,3,2,4,7,6]$$ and $$R = [12,9,15,10,11,14,13]$$.
3. Then we have max heap HL as shown below:

1. Then we have min heap HR as shown below:

1. Then we fill in the structure of T as follows:

The dotted lines represent the underlying structure of each original heap.

### Analysis

The running time is as follows:

• $$O(n)$$ for finding the median.
• $$O(n)$$ for constructing the two heaps.
• $$O(n)$$ for merging the two heaps.

Thus, the total time is still $$O(n)$$.

• That's very elegant, thanks! – Yariv Levy Mar 20 '19 at 6:39

We can do this similar to the linear construction of a heap.

We will start with the leaves. We need to determine what elements will be left child leaves and which will be right child leaves.

Assume w.l.o.g. that $$n = 2^k - 1$$. There will be $$2^{k-1}$$ leaves where $$2^{k-2}$$ will be left children, and the other $$2^{k-2}$$ will be right children.

Since we know every left child must be less than it's parent, we can guarantee this by using the smallest $$2^{k-2}$$ elements for left child leaves. Similarly we use the largest $$2^{k-2}$$ elements for right child leaves. The recursive procedure is as follows (building from the leaves to the root).

build-tree(list A of length n):
if n == 1:
return singleton tree of the 1 element in A.

let n = 2^k - 1
let l = 2^(k-2)         # rank of  left partition element
let r = n - 2^(k-2) + 1 # rank of right partition element

l_elem = SELECT(l, A)   # linear time select
r_elem = SELECT(r, A)   # linear time select

let L be all elements in A <= l_elem
let R be all elements in A >= r_elem
let C be all elements in A that are not in L or R

let tree T = build-tree(C)

for i in {0 ... l}:
let L[i] be the  left child of leaf i in T
let R[i] be the right child of leaf i in T

return T


Let's try an example on $$[8,12,9,15,5,1,10,3,11,14,2,4,13,7,6]$$. The L, R, and Cs would be as follows:

1. $$L = [1, 3, 2, 4]$$, $$C = [8, 9, 5, 10, 11, 7, 6]$$, $$R = [12, 15, 14, 13]$$
2. $$L = [5, 6]$$, $$C = [8, 9, 7]$$, $$R = [10, 11]$$
3. $$L = [7]$$, $$C = [8]$$, $$R = [9]$$
4. return TreeNode(8).

Then it would recursively build the following tree:

### Analysis

We get the following recurrence:

$$T(2^k - 1) = T(2^{k-1} - 1) + O(n)$$

This comes out to be $$O(n)$$.