# coding: utf-8

# # Practice: Build a recursive data structure

# You are given an array of floating point numbers called `numbers`. These numbers lie between 0 and 1.
# 
# Write a function `build_tree(numbers, left, right, max_in_leaf=5)` that builds a "tree of bins" data structure, where
# 
# * `left` is a lower bound on *numbers*
# * `right` is an upper bound on *numbers*
# * `max_in_leaf` is the largest number of numbers allowed in a leaf node of the tree
# 
# Have this function do the following:
# 
# * If there are fewer numbers in `numbers` than max_in_leaf, return `numbers` unmodified as a 'leaf node'.
# * Otherwise, return a tuple of the form `(left_child, pivot, right_child)`, where `pivot` is the average of `left` and `right`. `left_child` is the result of processing the part of `numbers` that is less than `pivot` through `build_tree`, and `right_child` is the same for the numbers larger than `pivot`.
# 
# Hints:
# 
# * look up `len()` to find the length of `numbers`, or use `numbers.shape[0]`

# In[2]:

import numpy as np

numbers = np.random.rand(100)


# In[3]:

def build_tree(numbers, left, right, max_in_leaf=5):
    # ...
    pass


# In[4]:

# Solution

def build_tree(numbers, left, right, max_in_leaf=5):
    if len(numbers) <= max_in_leaf:
        return numbers

    pivot = (left + right)/2
    return (build_tree(numbers[numbers < pivot], left, pivot, max_in_leaf),
            pivot,
            build_tree(numbers[numbers >= pivot], pivot, right, max_in_leaf))


# In[5]:

tree = build_tree(numbers, 0, 1)
print(tree)


# In[ ]: