A not uncommon interview question is to construct a binary search tree from a list of sorted numbers. This is actually very simple. Let us start with the definition of the data structure. The following class `Node` has a value and a left and right sub-tree.

class Node(object): def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right

We now can create a tree as follows:

tree = Node(1, Node(11, Node(111), Node(112)), Node(12))

To print out a tree we define a method `show` that recursively traverses the tree nodes and prints out the node values, indented by their tree depths:

def show(node, depths=0): if not node: return print " "*depths + str(node.value) show(node.left, level+2) show(node.right, level+2)

If we run `show(tree)`, we get the following output:

1 11 111 112 12

Now everything is in place. The following function `construct` takes a list of sorted numbers and recursively creates the binary search tree.

def construct(numbers): if not numbers: return None mid = len(numbers) // 2 return Node(numbers[mid], construct(numbers[:mid]), construct(numbers[mid+1:]))

The first line checks whether the numbers list is empty. In this case we are done and returning `None`. Otherwise we find the index `mid` of the element in the middle of the numbers list (This is Python 3k and we perform an integer division with '`//`'. In Python 2.x a simple '/' would do). Now comes the elegant part.

To construct the tree, we create and return a node that contains the number at the middle position as value (*`numbers[mid]`). The left sub-tree of the node is created by calling `construct` for the numbers to the left of the middle element (`numbers[:mid]`) and the right sub-tree is created by calling `construct` for the numbers to the right of the middle element (`numbers[mid+1:]`).
That's it! Let's try it out:

numbers = [1,5,7,10,40,50] show( construct(numbers) ) 10 5 1 7 50 40

Too easy ;)