Hackbright Code Challenges

Make Binary Search Tree: Solution

Make Binary Search Tree: Solution

Problem

Make Binary Search Tree

Challenge

Medium

Concepts

Trees, Recursion

Download

make-bst-solution.zip


A good solution is:

makebst.py
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.