iterative version of recursive algorithm to make a binary tree

Question

Given this algorithm, I would like to know if there exists an iterative version. Also, I want to know if the iterative version can be faster.

This some kind of pseudo-python...

the algorithm returns a reference to root of the tree

make_tree(array a)
  if len(a) == 0
        return None;

  node = pick a random point from the array
  calculate distances of the point against the others
  calculate median of such distances
  node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances)
  node.right = make_tree(subset, such the distance is greater or equal to the median)
  return node

Answer 1

A recursive function with only one recursive call can usually be turned into a tail-recursive function without too much effort, and then it's trivial to convert it into an iterative function. The canonical example here is factorial:

# naïve recursion
def fac(n):
    if n <= 1:
        return 1
    else:
        return n * fac(n - 1)

# tail-recursive with accumulator
def fac(n):
    def fac_helper(m, k):
        if m <= 1:
            return k
        else:
            return fac_helper(m - 1, m * k)
    return fac_helper(n, 1)

# iterative with accumulator
def fac(n):
    k = 1
    while n > 1:
        n, k = n - 1, n * k
    return k

However, your case here involves two recursive calls, and unless you significantly rework your algorithm, you need to keep a stack. Managing your own stack may be a little faster than using Python's function call stack, but the added speed and depth will probably not be worth the complexity. The canonical example here would be the Fibonacci sequence:

# naïve recursion
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

# tail-recursive with accumulator and stack
def fib(n):
    def fib_helper(m, k, stack):
        if m <= 1:
            if stack:
                m = stack.pop()
                return fib_helper(m, k + 1, stack)
            else:
                return k + 1
        else:
            stack.append(m - 2)
            return fib_helper(m - 1, k, stack)
    return fib_helper(n, 0, [])

# iterative with accumulator and stack
def fib(n):
    k, stack = 0, []
    while 1:
        if n <= 1:
            k = k + 1
            if stack:
                n = stack.pop()
            else:
                break
        else:
            stack.append(n - 2)
            n = n - 1
    return k

Now, your case is a lot tougher than this: a simple accumulator will have difficulties expressing a partly-built tree with a pointer to where a subtree needs to be generated. You'll want a zipper -- not easy to implement in a not-really-functional language like Python.