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