Make Binary Search Tree

Challenge

Medium

Concepts

Trees, Recursion

Download

make-bst.zip

Solution

Make Binary Search Tree: Solution

A binary search tree is a binary tree where all left-hand node values are less than or equal to the node value, and all right-hand node values are greater than the node value.

For example:

We’ve written a simple BinaryNode class for binary search tree nodes, with a data attribute and left and right child note attributes.

class BinaryNode(object):
    """Node in a binary tree."""

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

We’ve also provided the sub of a make_bst function:

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.
    """

When you run the makebst.py file, the tests do not pass. This is expected, as we haven’t implemented the make_bst function.

Your Task

Given a sorted Python list of integers, produce a balanced binary search tree from the list of integers.

For example, given the list nums = [1, 2, 3, 4, 5, 6, 7], you should produce the tree shown above.

If you can’t generate a perfectly-balanced tree, you should prefer to fill left-hand children over right-hand ones.

So, for example, nums = [1, 2, 3, 4] should give:

Implement the make_bst function.

Once you do this, all tests should pass.