{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Practice: Build a recursive data structure"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "You are given an array of floating point numbers called `numbers`. These numbers lie between 0 and 1.\n",
        "\n",
        "Write a function `build_tree(numbers, left, right, max_in_leaf=5)` that builds a \"tree of bins\" data structure, where\n",
        "\n",
        "* `left` is a lower bound on *numbers*\n",
        "* `right` is an upper bound on *numbers*\n",
        "* `max_in_leaf` is the largest number of numbers allowed in a leaf node of the tree\n",
        "\n",
        "Have this function do the following:\n",
        "\n",
        "* If there are fewer numbers in `numbers` than max_in_leaf, return `numbers` unmodified as a 'leaf node'.\n",
        "* 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`.\n",
        "\n",
        "Hints:\n",
        "\n",
        "* look up `len()` to find the length of `numbers`, or use `numbers.shape[0]`"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "\n",
        "numbers = np.random.rand(100)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "def build_tree(numbers, left, right, max_in_leaf=5):\n",
        "    # ...\n",
        "    pass"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Solution\n",
        "\n",
        "def build_tree(numbers, left, right, max_in_leaf=5):\n",
        "    if len(numbers) <= max_in_leaf:\n",
        "        return numbers\n",
        "\n",
        "    pivot = (left + right)/2\n",
        "    return (build_tree(numbers[numbers < pivot], left, pivot, max_in_leaf),\n",
        "            pivot,\n",
        "            build_tree(numbers[numbers >= pivot], pivot, right, max_in_leaf))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "((((array([ 0.03155442,  0.04969038,  0.00203516,  0.01134467]), 0.0625, array([ 0.08795129,  0.08484712,  0.10400076])), 0.125, ((array([ 0.13288577,  0.1348917 ,  0.13717107,  0.13363111]), 0.15625, array([ 0.18361257,  0.16379185,  0.17935313])), 0.1875, array([ 0.18835925]))), 0.25, ((((array([ 0.25471829,  0.25316833,  0.25368532]), 0.265625, array([ 0.2753575 ,  0.273414  ,  0.27016936])), 0.28125, array([ 0.31082018,  0.29369432,  0.29940896,  0.30908776])), 0.3125, array([ 0.33571279,  0.37308478,  0.33152007,  0.35286179])), 0.375, (array([ 0.42385846,  0.4181284 ,  0.41651459,  0.40505667,  0.39770273]), 0.4375, (array([ 0.45339789,  0.45886606,  0.45242226,  0.46320172]), 0.46875, array([ 0.47478645,  0.47411047]))))), 0.5, (((((array([ 0.50499705,  0.50985016]), 0.515625, array([ 0.52229993,  0.51933766,  0.51886349,  0.52999165,  0.52412507])), 0.53125, array([ 0.55858432,  0.54768638,  0.55832187,  0.5325089 ,  0.55220628])), 0.5625, (array([ 0.57673859,  0.56823789,  0.5813294 ,  0.58937822]), 0.59375, array([ 0.6160641 ,  0.61934406,  0.602265  ,  0.6162048 ]))), 0.625, (array([ 0.65624928,  0.6413943 ,  0.67663038,  0.64642908]), 0.6875, (array([ 0.70809202,  0.68992577,  0.70079716,  0.70850778]), 0.71875, array([ 0.74158749,  0.73977694,  0.73835865])))), 0.75, (((array([ 0.77388481,  0.75894454,  0.75947687,  0.75107273,  0.75294742]), 0.78125, array([ 0.81109003,  0.79674588,  0.78627348,  0.80242775,  0.79621333])), 0.8125, array([ 0.85778992,  0.8153317 ,  0.8164691 ,  0.84316018])), 0.875, ((array([ 0.88278667,  0.88526777,  0.89802129]), 0.90625, array([ 0.92812108,  0.90822701,  0.91261268])), 0.9375, ((array([ 0.94584389,  0.95214282,  0.93878381,  0.94956855]), 0.953125, array([ 0.96443695,  0.96785209])), 0.96875, array([ 0.9805466 ,  0.97100946,  0.99383466]))))))\n"
          ]
        }
      ],
      "source": [
        "tree = build_tree(numbers, 0, 1)\n",
        "print(tree)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.5.1+"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}