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!

  • 1
    $\begingroup$ What do you think? What have you tried? Please edit the question to show your thoughts, partial progress or where you got stuck. $\endgroup$ – John L. Mar 5 '19 at 13:05
  • $\begingroup$ Are you over there? $\endgroup$ – John L. Mar 6 '19 at 14:27
  • $\begingroup$ 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. $\endgroup$ – Yariv Levy Mar 7 '19 at 9:50
  • $\begingroup$ 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. $\endgroup$ – ryan Mar 19 '19 at 21:45
  • $\begingroup$ @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. $\endgroup$ – Yariv Levy Mar 19 '19 at 21:47

Answer #2.

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.


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)$.

| cite | improve this answer | |
  • $\begingroup$ That's very elegant, thanks! $\endgroup$ – 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:



We get the following recurrence:

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

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.