Trees, Recursion
A good solution is:
def make_bst(nums):
"""Given a list of sorted numbers, make a binary search tree.
Returns the root node of a new BST that is valid and balanced.
"""
# START SOLUTION
# Base case: when there's nothing in the list
if not nums:
return None
# Find midpoint
mid_index = len(nums) // 2
# Make new node out of midpoint
node = BinaryNode(nums[mid_index])
# Recursively find new left- and right-hand nodes
node.left = make_bst(nums[:mid_index])
node.right = make_bst(nums[mid_index + 1:])
return node
The solution is rather elegant—we find the mid-point in the list, use that as our start node, then recurse on the everything-before-midpoint and everything-after-midpoint lists, making the nodes returned by that into our left and right nodes.
Of course, like any recursive solution, this could also be written in a loop—but it would be trickier code to write.