Construct binary search tree from sorted numbers

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 ;)