labs/trees/binary-trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor\n",
    "from dtreeviz.trees import *\n",
    "from lolviz import *\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "%config InlineBackend.figure_format = 'retina'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Setup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make sure to install stuff:\n",
    "\n",
    "```\n",
    "pip install -U dtreeviz\n",
    "pip install -U lolviz\n",
    "brew install graphviz\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary tree class definition\n",
    "\n",
    "A binary tree has a payload (a value) and references to left and right children. One or both of the children references can be `None`.   A reference to a node is the same thing as a reference to a tree as the tree is a self similar data structure. We don't distinguish between the two kinds of references. A reference to the root node is a reference to the entire tree.\n",
    "\n",
    "Here is a basic tree node class in Python. The constructor requires at least a value to store in the node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "  def __init__(self, value, left=None, right=None):\n",
    "    self.value = value\n",
    "    self.left = left\n",
    "    self.right = right\n",
    "  def __repr__(self):\n",
    "    return str(self.value)\n",
    "  def __str__(self):\n",
    "    return str(self.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Manual tree construction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's how to create and visualize a single node:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.49.1 (20210923.0004)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"60pt\" height=\"64pt\"\n",
       " viewBox=\"0.00 0.00 60.00 64.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 60)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-60 56,-60 56,4 -4,4\"/>\n",
       "<!-- node140572551605408 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140572551605408</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"52,-56 0,-56 0,0 52,0 52,-56\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-40 2,-54 50,-54 50,-40 2,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-40 50,-40 \"/>\n",
       "<text text-anchor=\"start\" x=\"4.5\" y=\"-44.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-38 2,-40 50,-40 50,-38 2,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-24 2,-38 34,-38 34,-24 2,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-24 34,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-24 34,-38 50,-38 50,-24 34,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"35\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-21 50,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-19 2,-21 50,-21 50,-19 2,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-10 2,-19 34,-19 34,-10 2,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-10 34,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-10 34,-19 34,-19 34,-10 34,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-10 34,-19 50,-19 50,-10 34,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"37\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-7 2,-10 34,-10 34,-7 2,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-7 34,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"17.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-7 34,-10 34,-10 34,-7 34,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-7 34,-10 50,-10 50,-7 34,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"41.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-2 2,-7 34,-7 34,-2 2,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-2 34,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"17.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-2 34,-7 34,-7 34,-2 34,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-2 34,-7 50,-7 50,-2 34,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"41.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fd99900ef10>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root = TreeNode(1)\n",
    "treeviz(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Given `left` and `right` nodes,  create node `root` with those nodes as children.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.49.1 (20210923.0004)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"80pt\" height=\"22pt\"\n",
       " viewBox=\"0.00 0.00 80.00 22.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 18)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-18 76,-18 76,4 -4,4\"/>\n",
       "<!-- node4329274912 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node4329274912</title>\n",
       "<text text-anchor=\"start\" x=\"2\" y=\"-4.8\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"9.00\" fill=\"#444443\">&lt;ellipsis:Ellipsis&gt;</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fd99903e220>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "left = TreeNode(2)\n",
    "right = TreeNode(3)\n",
    "root = ...\n",
    "treeviz(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "left = TreeNode(2)\n",
    "right = TreeNode(3)\n",
    "root = TreeNode(1,left,right)\n",
    "treeviz(root)\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Write code to create the following tree structure**\n",
    "\n",
    "<img src=\"3-level-tree.png\" width=\"30%\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.49.1 (20210923.0004)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"80pt\" height=\"22pt\"\n",
       " viewBox=\"0.00 0.00 80.00 22.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 18)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-18 76,-18 76,4 -4,4\"/>\n",
       "<!-- node4329274912 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node4329274912</title>\n",
       "<text text-anchor=\"start\" x=\"2\" y=\"-4.8\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"9.00\" fill=\"#444443\">&lt;ellipsis:Ellipsis&gt;</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fd99900ed00>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "left = ...\n",
    "right = ...\n",
    "root = ...\n",
    "treeviz(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "left = TreeNode(2,TreeNode(4))\n",
    "right = TreeNode(3,TreeNode(5),TreeNode(6))\n",
    "root = TreeNode(1,left,right)\n",
    "treeviz(root)\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Walking trees manually\n",
    "\n",
    "To walk a tree, we simply follow the left and right children references, avoiding any `None` references."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q.** Given tree `r` shown here, what Python expressions refer to the nodes with 443 and 17 in them?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.49.1 (20210923.0004)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"150pt\" height=\"220pt\"\n",
       " viewBox=\"0.00 0.00 150.00 220.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 216)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-216 146,-216 146,4 -4,4\"/>\n",
       "<!-- node140572551801680 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140572551801680</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"105,-212 47,-212 47,-156 105,-156 105,-212\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"49,-196 49,-210 103,-210 103,-196 49,-196\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"49,-196 103,-196 \"/>\n",
       "<text text-anchor=\"start\" x=\"54.5\" y=\"-200.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"49,-194 49,-196 103,-196 103,-194 49,-194\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"49,-180 49,-194 81,-194 81,-180 49,-180\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"81,-180 81,-194 \"/>\n",
       "<text text-anchor=\"start\" x=\"50\" y=\"-184.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"81,-180 81,-194 103,-194 103,-180 81,-180\"/>\n",
       "<text text-anchor=\"start\" x=\"82\" y=\"-184.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;10&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"49,-177 103,-177 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"49,-175 49,-177 103,-177 103,-175 49,-175\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"49,-166 49,-175 81,-175 81,-166 49,-166\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"81,-166 81,-175 \"/>\n",
       "<text text-anchor=\"start\" x=\"50\" y=\"-169.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"81,-166 81,-175 81,-175 81,-166 81,-166\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"81,-166 81,-175 103,-175 103,-166 81,-166\"/>\n",
       "<text text-anchor=\"start\" x=\"90\" y=\"-169.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"49,-163 49,-166 81,-166 81,-163 49,-163\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"81,-163 81,-166 \"/>\n",
       "<text text-anchor=\"start\" x=\"64.5\" y=\"-164.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"81,-163 81,-166 81,-166 81,-163 81,-163\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"81,-163 81,-166 103,-166 103,-163 81,-163\"/>\n",
       "<text text-anchor=\"start\" x=\"91.5\" y=\"-164.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"49,-158 49,-163 81,-163 81,-158 49,-158\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"81,-158 81,-163 \"/>\n",
       "<text text-anchor=\"start\" x=\"64.5\" y=\"-159.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"81,-158 81,-163 81,-163 81,-158 81,-158\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"81,-158 81,-163 103,-163 103,-158 81,-158\"/>\n",
       "<text text-anchor=\"start\" x=\"91.5\" y=\"-159.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551801584 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>node140572551801584</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"77,-134 13,-134 13,-78 77,-78 77,-134\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"15,-118 15,-132 75,-132 75,-118 15,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"15,-118 75,-118 \"/>\n",
       "<text text-anchor=\"start\" x=\"23.5\" y=\"-122.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"15,-116 15,-118 75,-118 75,-116 15,-116\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"15,-102 15,-116 47,-116 47,-102 15,-102\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"47,-102 47,-116 \"/>\n",
       "<text text-anchor=\"start\" x=\"16\" y=\"-106.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"47,-102 47,-116 75,-116 75,-102 47,-102\"/>\n",
       "<text text-anchor=\"start\" x=\"48\" y=\"-106.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;443&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"15,-99 75,-99 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"15,-97 15,-99 75,-99 75,-97 15,-97\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"15,-88 15,-97 47,-97 47,-88 15,-88\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"47,-88 47,-97 \"/>\n",
       "<text text-anchor=\"start\" x=\"16\" y=\"-91.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"47,-88 47,-97 47,-97 47,-88 47,-88\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"47,-88 47,-97 75,-97 75,-88 47,-88\"/>\n",
       "<text text-anchor=\"start\" x=\"62\" y=\"-91.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"15,-85 15,-88 47,-88 47,-85 15,-85\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"47,-85 47,-88 \"/>\n",
       "<text text-anchor=\"start\" x=\"30.5\" y=\"-86.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"47,-85 47,-88 47,-88 47,-85 47,-85\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"47,-85 47,-88 75,-88 75,-85 47,-85\"/>\n",
       "<text text-anchor=\"start\" x=\"60.5\" y=\"-86.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"15,-80 15,-85 47,-85 47,-80 15,-80\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"47,-80 47,-85 \"/>\n",
       "<text text-anchor=\"start\" x=\"30.5\" y=\"-81.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"47,-80 47,-85 47,-85 47,-80 47,-80\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"47,-80 47,-85 75,-85 75,-80 47,-80\"/>\n",
       "<text text-anchor=\"start\" x=\"60.5\" y=\"-81.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551801680&#45;&gt;node140572551801584 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>node140572551801680:c&#45;&gt;node140572551801584</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M63.88,-159.85C62.29,-155.41 59.23,-146.84 56.03,-137.87\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"64.46\" cy=\"-161.49\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"57.31,-137.31 54.65,-134.02 54.68,-138.25 57.31,-137.31\"/>\n",
       "</g>\n",
       "<!-- node140572551800768 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>node140572551800768</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"142,-134 84,-134 84,-78 142,-78 142,-134\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"86,-118 86,-132 140,-132 140,-118 86,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"86,-118 140,-118 \"/>\n",
       "<text text-anchor=\"start\" x=\"91.5\" y=\"-122.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"86,-116 86,-118 140,-118 140,-116 86,-116\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"86,-102 86,-116 118,-116 118,-102 86,-102\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"118,-102 118,-116 \"/>\n",
       "<text text-anchor=\"start\" x=\"87\" y=\"-106.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-102 118,-116 140,-116 140,-102 118,-102\"/>\n",
       "<text text-anchor=\"start\" x=\"119\" y=\"-106.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;17&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"86,-99 140,-99 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"86,-97 86,-99 140,-99 140,-97 86,-97\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"86,-88 86,-97 118,-97 118,-88 86,-88\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"118,-88 118,-97 \"/>\n",
       "<text text-anchor=\"start\" x=\"87\" y=\"-91.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-88 118,-97 118,-97 118,-88 118,-88\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-88 118,-97 140,-97 140,-88 118,-88\"/>\n",
       "<text text-anchor=\"start\" x=\"127\" y=\"-91.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"86,-85 86,-88 118,-88 118,-85 86,-85\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"118,-85 118,-88 \"/>\n",
       "<text text-anchor=\"start\" x=\"101.5\" y=\"-86.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-85 118,-88 118,-88 118,-85 118,-85\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-85 118,-88 140,-88 140,-85 118,-85\"/>\n",
       "<text text-anchor=\"start\" x=\"128.5\" y=\"-86.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"86,-80 86,-85 118,-85 118,-80 86,-80\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"118,-80 118,-85 \"/>\n",
       "<text text-anchor=\"start\" x=\"101.5\" y=\"-81.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-80 118,-85 118,-85 118,-80 118,-80\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-80 118,-85 140,-85 140,-80 118,-80\"/>\n",
       "<text text-anchor=\"start\" x=\"128.5\" y=\"-81.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551801680&#45;&gt;node140572551800768 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>node140572551801680:c&#45;&gt;node140572551800768</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M93.18,-159.85C94.85,-155.41 98.06,-146.84 101.42,-137.87\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"92.56\" cy=\"-161.5\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"102.78,-138.25 102.87,-134.02 100.15,-137.27 102.78,-138.25\"/>\n",
       "</g>\n",
       "<!-- node140572551801344 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>node140572551801344</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"62,-56 0,-56 0,0 62,0 62,-56\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-40 2,-54 60,-54 60,-40 2,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-40 60,-40 \"/>\n",
       "<text text-anchor=\"start\" x=\"9.5\" y=\"-44.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-38 2,-40 60,-40 60,-38 2,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-24 2,-38 34,-38 34,-24 2,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-24 34,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-24 34,-38 60,-38 60,-24 34,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"35\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;&#45;34&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-21 60,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-19 2,-21 60,-21 60,-19 2,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-10 2,-19 34,-19 34,-10 2,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-10 34,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-10 34,-19 34,-19 34,-10 34,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-10 34,-19 60,-19 60,-10 34,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"47\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-7 2,-10 34,-10 34,-7 2,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-7 34,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"17.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-7 34,-10 34,-10 34,-7 34,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-7 34,-10 60,-10 60,-7 34,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"46.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-2 2,-7 34,-7 34,-2 2,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-2 34,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"17.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-2 34,-7 34,-7 34,-2 34,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-2 34,-7 60,-7 60,-2 34,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"46.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551801584&#45;&gt;node140572551801344 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>node140572551801584:c&#45;&gt;node140572551801344</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M31,-81.52C31,-77.05 31,-68.86 31,-60.26\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"31\" cy=\"-83.4\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"32.4,-60.02 31,-56.02 29.6,-60.02 32.4,-60.02\"/>\n",
       "</g>\n",
       "<!-- node140572551801200 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>node140572551801200</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"131,-56 73,-56 73,0 131,0 131,-56\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"75,-40 75,-54 129,-54 129,-40 75,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"75,-40 129,-40 \"/>\n",
       "<text text-anchor=\"start\" x=\"80.5\" y=\"-44.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"75,-38 75,-40 129,-40 129,-38 75,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"75,-24 75,-38 107,-38 107,-24 75,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-24 107,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"76\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-24 107,-38 129,-38 129,-24 107,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"108\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;99&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"75,-21 129,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"75,-19 75,-21 129,-21 129,-19 75,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"75,-10 75,-19 107,-19 107,-10 75,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-10 107,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"76\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-10 107,-19 107,-19 107,-10 107,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-10 107,-19 129,-19 129,-10 107,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"116\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"75,-7 75,-10 107,-10 107,-7 75,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-7 107,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"90.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-7 107,-10 107,-10 107,-7 107,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-7 107,-10 129,-10 129,-7 107,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"117.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"75,-2 75,-7 107,-7 107,-2 75,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-2 107,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"90.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-2 107,-7 107,-7 107,-2 107,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-2 107,-7 129,-7 129,-2 107,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"117.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551800768&#45;&gt;node140572551801200 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>node140572551800768:c&#45;&gt;node140572551801200</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M102,-81.52C102,-77.05 102,-68.86 102,-60.26\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"102\" cy=\"-83.4\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"103.4,-60.02 102,-56.02 100.6,-60.02 103.4,-60.02\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fd99903ec40>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "left = TreeNode(443,TreeNode(-34))\n",
    "right = TreeNode(17,TreeNode(99))\n",
    "r = TreeNode(10,left,right)\n",
    "treeviz(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "r.left, r.right\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q.** Given the same tree `r`, what Python expressions refer to the nodes with -34 and 99 in them?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "<pre>\n",
    "r.left.left, r.right.left\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Walking all nodes\n",
    "\n",
    "Now let's create a function to walk all nodes in a tree. Remember that our template for creating any recursive function looks like this:\n",
    "\n",
    "```\n",
    "def f(input):\n",
    "    1. check termination condition\n",
    "    2. process the active input region / current node, etc…\n",
    "    3. invoke f on subregion(s)\n",
    "    4. combine and return results\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def walk(p:TreeNode):\n",
    "    if p is None: return           # step 1\n",
    "    print(p.value)                 # step 2\n",
    "    walk(p.left)                   # step 3\n",
    "    walk(p.right)                  # step 3 (there is no step 4 for this problem)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's create the simple 3-level tree we had before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.49.1 (20210923.0004)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"178pt\" height=\"220pt\"\n",
       " viewBox=\"0.00 0.00 178.00 220.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 216)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-216 174,-216 174,4 -4,4\"/>\n",
       "<!-- node140572551605840 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140572551605840</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"85,-212 33,-212 33,-156 85,-156 85,-212\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"35,-196 35,-210 83,-210 83,-196 35,-196\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"35,-196 83,-196 \"/>\n",
       "<text text-anchor=\"start\" x=\"37.5\" y=\"-200.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"35,-194 35,-196 83,-196 83,-194 35,-194\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"35,-180 35,-194 67,-194 67,-180 35,-180\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"67,-180 67,-194 \"/>\n",
       "<text text-anchor=\"start\" x=\"36\" y=\"-184.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"67,-180 67,-194 83,-194 83,-180 67,-180\"/>\n",
       "<text text-anchor=\"start\" x=\"68\" y=\"-184.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"35,-177 83,-177 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"35,-175 35,-177 83,-177 83,-175 35,-175\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"35,-166 35,-175 67,-175 67,-166 35,-166\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"67,-166 67,-175 \"/>\n",
       "<text text-anchor=\"start\" x=\"36\" y=\"-169.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"67,-166 67,-175 67,-175 67,-166 67,-166\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"67,-166 67,-175 83,-175 83,-166 67,-166\"/>\n",
       "<text text-anchor=\"start\" x=\"70\" y=\"-169.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"35,-163 35,-166 67,-166 67,-163 35,-163\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"67,-163 67,-166 \"/>\n",
       "<text text-anchor=\"start\" x=\"50.5\" y=\"-164.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"67,-163 67,-166 67,-166 67,-163 67,-163\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"67,-163 67,-166 83,-166 83,-163 67,-163\"/>\n",
       "<text text-anchor=\"start\" x=\"74.5\" y=\"-164.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"35,-158 35,-163 67,-163 67,-158 35,-158\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"67,-158 67,-163 \"/>\n",
       "<text text-anchor=\"start\" x=\"50.5\" y=\"-159.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"67,-158 67,-163 67,-163 67,-158 67,-158\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"67,-158 67,-163 83,-163 83,-158 67,-158\"/>\n",
       "<text text-anchor=\"start\" x=\"74.5\" y=\"-159.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551605168 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>node140572551605168</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"60,-134 8,-134 8,-78 60,-78 60,-134\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"10,-118 10,-132 58,-132 58,-118 10,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"10,-118 58,-118 \"/>\n",
       "<text text-anchor=\"start\" x=\"12.5\" y=\"-122.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"10,-116 10,-118 58,-118 58,-116 10,-116\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"10,-102 10,-116 42,-116 42,-102 10,-102\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"42,-102 42,-116 \"/>\n",
       "<text text-anchor=\"start\" x=\"11\" y=\"-106.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"42,-102 42,-116 58,-116 58,-102 42,-102\"/>\n",
       "<text text-anchor=\"start\" x=\"43\" y=\"-106.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;2&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"10,-99 58,-99 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"10,-97 10,-99 58,-99 58,-97 10,-97\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"10,-88 10,-97 42,-97 42,-88 10,-88\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"42,-88 42,-97 \"/>\n",
       "<text text-anchor=\"start\" x=\"11\" y=\"-91.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"42,-88 42,-97 42,-97 42,-88 42,-88\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"42,-88 42,-97 58,-97 58,-88 42,-88\"/>\n",
       "<text text-anchor=\"start\" x=\"45\" y=\"-91.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"10,-85 10,-88 42,-88 42,-85 10,-85\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"42,-85 42,-88 \"/>\n",
       "<text text-anchor=\"start\" x=\"25.5\" y=\"-86.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"42,-85 42,-88 42,-88 42,-85 42,-85\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"42,-85 42,-88 58,-88 58,-85 42,-85\"/>\n",
       "<text text-anchor=\"start\" x=\"49.5\" y=\"-86.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"10,-80 10,-85 42,-85 42,-80 10,-80\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"42,-80 42,-85 \"/>\n",
       "<text text-anchor=\"start\" x=\"25.5\" y=\"-81.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"42,-80 42,-85 42,-85 42,-80 42,-80\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"42,-80 42,-85 58,-85 58,-80 42,-80\"/>\n",
       "<text text-anchor=\"start\" x=\"49.5\" y=\"-81.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551605840&#45;&gt;node140572551605168 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>node140572551605840:c&#45;&gt;node140572551605168</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M50.04,-159.85C48.7,-155.41 46.09,-146.84 43.37,-137.87\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"50.54\" cy=\"-161.47\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"44.7,-137.44 42.2,-134.02 42.02,-138.25 44.7,-137.44\"/>\n",
       "</g>\n",
       "<!-- node140572551605312 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>node140572551605312</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"119,-134 67,-134 67,-78 119,-78 119,-134\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69,-118 69,-132 117,-132 117,-118 69,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"69,-118 117,-118 \"/>\n",
       "<text text-anchor=\"start\" x=\"71.5\" y=\"-122.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69,-116 69,-118 117,-118 117,-116 69,-116\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69,-102 69,-116 101,-116 101,-102 69,-102\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"101,-102 101,-116 \"/>\n",
       "<text text-anchor=\"start\" x=\"70\" y=\"-106.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"101,-102 101,-116 117,-116 117,-102 101,-102\"/>\n",
       "<text text-anchor=\"start\" x=\"102\" y=\"-106.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;3&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"69,-99 117,-99 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69,-97 69,-99 117,-99 117,-97 69,-97\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69,-88 69,-97 101,-97 101,-88 69,-88\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"101,-88 101,-97 \"/>\n",
       "<text text-anchor=\"start\" x=\"70\" y=\"-91.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"101,-88 101,-97 101,-97 101,-88 101,-88\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"101,-88 101,-97 117,-97 117,-88 101,-88\"/>\n",
       "<text text-anchor=\"start\" x=\"104\" y=\"-91.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69,-85 69,-88 101,-88 101,-85 69,-85\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"101,-85 101,-88 \"/>\n",
       "<text text-anchor=\"start\" x=\"84.5\" y=\"-86.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"101,-85 101,-88 101,-88 101,-85 101,-85\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"101,-85 101,-88 117,-88 117,-85 101,-85\"/>\n",
       "<text text-anchor=\"start\" x=\"108.5\" y=\"-86.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"69,-80 69,-85 101,-85 101,-80 69,-80\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"101,-80 101,-85 \"/>\n",
       "<text text-anchor=\"start\" x=\"84.5\" y=\"-81.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"101,-80 101,-85 101,-85 101,-80 101,-80\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"101,-80 101,-85 117,-85 117,-80 101,-80\"/>\n",
       "<text text-anchor=\"start\" x=\"108.5\" y=\"-81.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551605840&#45;&gt;node140572551605312 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>node140572551605840:c&#45;&gt;node140572551605312</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M76.01,-159.85C77.44,-155.41 80.19,-146.84 83.08,-137.87\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"75.49\" cy=\"-161.48\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"84.43,-138.25 84.32,-134.02 81.76,-137.4 84.43,-138.25\"/>\n",
       "</g>\n",
       "<!-- node140572551802640 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>node140572551802640</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"52,-56 0,-56 0,0 52,0 52,-56\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-40 2,-54 50,-54 50,-40 2,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-40 50,-40 \"/>\n",
       "<text text-anchor=\"start\" x=\"4.5\" y=\"-44.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-38 2,-40 50,-40 50,-38 2,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-24 2,-38 34,-38 34,-24 2,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-24 34,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-24 34,-38 50,-38 50,-24 34,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"35\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;4&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-21 50,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-19 2,-21 50,-21 50,-19 2,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-10 2,-19 34,-19 34,-10 2,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-10 34,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-10 34,-19 34,-19 34,-10 34,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-10 34,-19 50,-19 50,-10 34,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"37\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-7 2,-10 34,-10 34,-7 2,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-7 34,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"17.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-7 34,-10 34,-10 34,-7 34,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-7 34,-10 50,-10 50,-7 34,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"41.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-2 2,-7 34,-7 34,-2 2,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"34,-2 34,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"17.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-2 34,-7 34,-7 34,-2 34,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"34,-2 34,-7 50,-7 50,-2 34,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"41.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551605168&#45;&gt;node140572551802640 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>node140572551605168:c&#45;&gt;node140572551802640</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M26,-81.52C26,-77.05 26,-68.86 26,-60.26\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"26\" cy=\"-83.4\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"27.4,-60.02 26,-56.02 24.6,-60.02 27.4,-60.02\"/>\n",
       "</g>\n",
       "<!-- node140572551800048 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>node140572551800048</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"111,-56 59,-56 59,0 111,0 111,-56\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"61,-40 61,-54 109,-54 109,-40 61,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"61,-40 109,-40 \"/>\n",
       "<text text-anchor=\"start\" x=\"63.5\" y=\"-44.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"61,-38 61,-40 109,-40 109,-38 61,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"61,-24 61,-38 93,-38 93,-24 61,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"93,-24 93,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"62\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"93,-24 93,-38 109,-38 109,-24 93,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"94\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;5&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"61,-21 109,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"61,-19 61,-21 109,-21 109,-19 61,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"61,-10 61,-19 93,-19 93,-10 61,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"93,-10 93,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"62\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"93,-10 93,-19 93,-19 93,-10 93,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"93,-10 93,-19 109,-19 109,-10 93,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"96\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"61,-7 61,-10 93,-10 93,-7 61,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"93,-7 93,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"76.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"93,-7 93,-10 93,-10 93,-7 93,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"93,-7 93,-10 109,-10 109,-7 93,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"100.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"61,-2 61,-7 93,-7 93,-2 61,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"93,-2 93,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"76.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"93,-2 93,-7 93,-7 93,-2 93,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"93,-2 93,-7 109,-7 109,-2 93,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"100.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551605312&#45;&gt;node140572551800048 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>node140572551605312:c&#45;&gt;node140572551800048</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M85,-81.52C85,-77.05 85,-68.86 85,-60.26\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"85\" cy=\"-83.4\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"86.4,-60.02 85,-56.02 83.6,-60.02 86.4,-60.02\"/>\n",
       "</g>\n",
       "<!-- node140572551605552 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>node140572551605552</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"170,-56 118,-56 118,0 170,0 170,-56\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"120,-40 120,-54 168,-54 168,-40 120,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"120,-40 168,-40 \"/>\n",
       "<text text-anchor=\"start\" x=\"122.5\" y=\"-44.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"120,-38 120,-40 168,-40 168,-38 120,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"120,-24 120,-38 152,-38 152,-24 120,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"152,-24 152,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"121\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">value </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"152,-24 152,-38 168,-38 168,-24 152,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"153\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;6&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"120,-21 168,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"120,-19 120,-21 168,-21 168,-19 120,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"120,-10 120,-19 152,-19 152,-10 120,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"152,-10 152,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"121\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"152,-10 152,-19 152,-19 152,-10 152,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"152,-10 152,-19 168,-19 168,-10 152,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"155\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"120,-7 120,-10 152,-10 152,-7 120,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"152,-7 152,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"135.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"152,-7 152,-10 152,-10 152,-7 152,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"152,-7 152,-10 168,-10 168,-7 152,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"159.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"120,-2 120,-7 152,-7 152,-2 120,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"152,-2 152,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"135.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"152,-2 152,-7 152,-7 152,-2 152,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"152,-2 152,-7 168,-7 168,-2 152,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"159.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140572551605312&#45;&gt;node140572551605552 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>node140572551605312:c&#45;&gt;node140572551605552</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M110.76,-82.18C113.52,-77.77 119.12,-68.8 124.96,-59.47\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"109.85\" cy=\"-83.64\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"126.18,-60.15 127.12,-56.02 123.81,-58.67 126.18,-60.15\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fd99900ec10>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "left = TreeNode(2,TreeNode(4))\n",
    "right = TreeNode(3,TreeNode(5),TreeNode(6))\n",
    "root = TreeNode(1,left,right)\n",
    "treeviz(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q.** What is the output of running `walk(root)`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "    We walk the tree depth first, from left to right<p>\n",
    "<pre>\n",
    "1\n",
    "2\n",
    "4\n",
    "3\n",
    "5\n",
    "6\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Searching through nodes\n",
    "\n",
    "Here's how to search for an element as you walk, terminating as soon as the node with `x` is found:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(p:TreeNode, x:object):\n",
    "    print(\"enter \",p)\n",
    "    if p is None: return None\n",
    "    print(p)\n",
    "    if x==p.value:\n",
    "        return p\n",
    "    q = search(p.left, x)\n",
    "    if q is not None:\n",
    "        return q\n",
    "    q = search(p.right, x)\n",
    "    return q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q.** What is the output of running `search(root, 5)`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "    We walk the tree depth first as before, but now we stop when we reach the node with 5:<p>\n",
    "<pre>\n",
    "1\n",
    "2\n",
    "4\n",
    "3\n",
    "5\n",
    "</pre>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see the recursion entering and exiting (or discovering and finishing) nodes, here is a variation that prints out its progress through the tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(p:TreeNode, x:object):\n",
    "    if p is None: return None\n",
    "    print(\"enter \",p)\n",
    "    if x==p.value:\n",
    "        print(\"exit  \",p)\n",
    "        return p\n",
    "    q = search(p.left, x)\n",
    "    if q is not None:\n",
    "        print(\"exit  \",p)\n",
    "        return q\n",
    "    q = search(p.right, x)\n",
    "    print(\"exit  \",p)\n",
    "    return q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enter  1\n",
      "enter  2\n",
      "enter  4\n",
      "exit   4\n",
      "exit   2\n",
      "enter  3\n",
      "enter  5\n",
      "exit   5\n",
      "exit   3\n",
      "exit   1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search(root, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating (random) decision tree \"stumps\"\n",
    "\n",
    "A regression tree stump is a tree with a decision node at the root and two predictor leaves.  These are used by gradient boosting machines as the \"weak learners.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode: # acts as decision node and leaf. it's a leaf if split is None\n",
    "  def __init__(self, split=None, prediction=None, left=None, right=None):\n",
    "    self.split = split\n",
    "    self.prediction = prediction\n",
    "    self.left = left\n",
    "    self.right = right\n",
    "  def __repr__(self):\n",
    "    return str(self.value)\n",
    "  def __str__(self):\n",
    "    return str(self.value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sqfeet</th>\n",
       "      <th>rent</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>750</td>\n",
       "      <td>1160</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>800</td>\n",
       "      <td>1200</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>850</td>\n",
       "      <td>1280</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>900</td>\n",
       "      <td>1450</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>950</td>\n",
       "      <td>1300</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   sqfeet  rent\n",
       "0     750  1160\n",
       "1     800  1200\n",
       "2     850  1280\n",
       "3     900  1450\n",
       "4     950  1300"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = pd.DataFrame()\n",
    "df[\"sqfeet\"] = [750, 800, 850, 900,950]\n",
    "df[\"rent\"] = [1160, 1200, 1280, 1450,1300]\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following code shows where sklearn would do a split with a normal decision tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAEtCAYAAADUV2PCAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAABYlAAAWJQFJUiTwAAA+QElEQVR4nO3dedwVZf3/8dftDoosQQqWQEqKfvOr4IJtbtfHn+IalkkuWS7lkqKmqblbbqWihnu5lQYmkiCm17h/U1JBS9MKF8hEDRQ3FDfu3x+fOTAc5r7vc27OfeZe3s/Hg8e5mblm5jozc+Yz1zLXNDQ2NiIiIiLFWKHoDIiIiHRlCsQiIiIFUiAWEREpkAKxiIhIgRSIRURECqRALCIiUiAFYhERkQIpEIuIiBRIgVhERKRACsQiIiIFUiAWEREpkAKxiIhIgRSIRURECrRS0RmQjsUsNAI3xJgcWHReOiqzsC1wP/C9GJPrC87LA8CgGJNBReajs9PvZol6n3NmYVPgQmAY0As4M8bkjHpsu1IKxGUyF8msBcC/gJuAy2JMPql3vmQJszAGeKvoINZRmIUDgV4xJmPbaP39gSOB4em/vijoSDtgFlYCbgNWBk4F3gL+1kz6NYDj8PN4GLAO8GCMybZtmU8F4qbdAkwFGoC1gQOAi4ChwKEF5qto3YBPC87DGGAWcH2hueg4DgQGAWPbaP0bACcDLwOPAzu30XZEqvWF9N9xMSa/qiB9X+AM4HVgOrBW22VtCbURN21GjMlvY0xuijH5BTAC+A9wsFnoV1SmzEKPorYNEGOyMMbk4yLzUK2i91kXMB34bIzJuvgNq3Rh7ez3tnb6+WaF6V8FPh9jsnaMyS7Ah22TraWpRFyhGJMFZmEa8E1gPWBuaV5aNXcasAt+4OcBU4BTYkz+m12PWdgE+CXwFWBhmu64dH2Lq/PMwiDgJeBM4DngBGAjYDxewsEshHT6lsBqePX55TEmV5Zt88t4tcxmeBvJG8BfgbNiTKalafqkaXbHq2MW4KXO36c3IqV15bZ1mYWDgcPxGoOPgL+k6/+/snSNwA3AVcB5wObAB8AkYEyMyXs0I10eYGDmb4DBMSazzMKsNN/HpOsfgf8IB6fLD8GPVQA+A8wBbgXOiDFZULatio9rM/ndA7/DHoof4+uAh5tIuyp+LuyLn2ML07SnxZg8mUm3LWkbM9AD+BGwLvBvvOnkskzaWcDA9O/s/touxuSBTLoBeDvaTsAqwP8BP4ox+VdL3zHG5F3g3ZbStYZZ+Dz+G9gBPwZvA88DV8WY3JCmWQE4Cfh/wBeBPsBrwJ34sXojs75BLPldPYuX5DcAXgF+HmNynVlYF6/92h6v0vwjcFj6PUvruR74LvBZfL/tgv8GpwE/zh6vFr5fzX7DzWzjAbxGZHvgYmBbvKbvXryk+GJZ+gbgh8DB+Hn7KfBEuq37M+kG0cI1qhqV/jbNwobAUcA2+Hm/Yrr9K2NMrin73tuk/73OLFyX/j04xmRWXh5iTD7EC1x1pRJxddZLPxffXaU/2ifwAH0zcATelrwP8Gez0DOTdgh+Yd0auBQ4HegH3NXMNvcErgD+hJ98d6XrOhS4B1gD+DlwLPACcIVZyAbODYCIX6AuwYPlOKAR+N/Mdm7F2/nuwi/sZwGP4T/aZpmF84FrgI/xC9uF+A/yfrMwMmeRTfGA9nia7wgchF/8WrI/HhD/kf5d+jc3k2Zd4D5gNnA8cFmaz+H4sfo6fiNwRJqPo4BoFlbOfKeKj2tTzMI3gNuBnvj+vAz4FnB+TtqV8WN8OvAoS24kNkq3t3nOJn4EnAj8Fg9EbwGXmoXTM2nG4PtqHkvvr+cyaVYHHsIvuCfj58e2wB/Nwootfc+2krbvRXyf/R4/d8/Dg9XXMklXwY/zTOAXpMcTP6ceMAur5Kx+V/w3ODFd9l3gN2ZhX/w3+i6+LybgN0YXN5HNPwH98ZutsfiN5UNm4X8q+H61/g03Z3X85u0j/Fz5NTASP7fWLkt7E/Ar/IbnhPS79cR/I7vnrHtPcq5R1ajmt4mfm19P5x+P36B8DFxtFk7KpPs5cE7699XkXyvaBZWIm9bdLPRlSRvxD/G70cfLSgmX4XfNm8WYLL6TMgu34nfHx+AnMviJsSbw1RiTP6fTfmUWxuM/4DwbA5vEmCy+cKYltUvx0up3MmkvNwuXAMeahStjTF7ASwndgdExJo/lbSANKtsDV8SYHNncTslZdgP8x/BnYPsYk4/S6dfiJY7LzcJ6MSbZduVNgC9n7uSvMgtrAt8zC8c2VyqOMfmtWfgZ8HqMyW+bSDYYOCTG5Nqy6b/Bq562KCvd3ItfkPdlSbtzNcd1GWkAuwS/adsyxmReOv0q8juLHIlfYHaKMbk7s57LgWfwWpRty5b5IjC0lD+zMA4vyZ5iFn4dY/KfGJNJaee2bs3sr77AL2JMLshsdy5wAV46ubuJ5draRnhp9SfZvOX4EOgfY/JBZtqVZuER4Fo8UEwoW2YosFGMyWyA9Df4Mh6EfhxjclFmPb2BA8xCXo3NbGCvGJPGdD0T8RvMX+K1C7lq/RuuQF/gkhiTMZk8PISf92fg17fSzeO+wA9iTK7OpL0EP+8vMQuTS983tcw1qhWq+W3elFNjcDF+832iWfhljMnHMSbRLJQKB482c/4XToG4aWem/7Im4ndqwOIAtite3bgwDdwls/A7yh2BM9IL80jgsUwQLrkQ2LuJfNyZc4J/E1gV+HXZNgEm43eRO+B312+n0/cwC3+LMVmYs40P8IvZVmZhUFPVNk3YA79ZuaAUhAFiTOak1XdH4zcwT2SWeTSnOu0+fP8MwgPP8ngTPyaLmYUv4TcApwOrptXAJf+HV8XvCFxfzXFtJg/Dgc8DvywFYYAYk7fNwpUsuVMv2Q8vuU7POaYR+K5Z6FYWbH6XvUmIMfkovSDdDOyGl1IqsQgPCln3pZ9DKC4Ql87d7czC9U01B6RB4QNYfAPUA7+2lb7DViwbiCeVgnC6jrlm4Z94UBlXlvZh4Bvkn5sXZINSjMl0sxCBYBbWaOamsta/4Uqcl/1PjMnt6XfekzQQ4+fhu8CkJvJ1Bn5OZAsjedeoilXz20zzna2mXg0v7TfgtQvbABsCT7c2P0VQIG7a1Xh17crAl4CfAJ/D2+1KNsCr9w9K/+Uptb/0w0+Yf+akyZtWktdGNzT9TJpZrtTb7/f4j+tk4Bjzdu678Tvx2bD4Aj4GL8G9ZBaexS9ik2JM7m1mG5C2vQJ/z5lXumh9gaUD8Ys5aUvteJ9pYXuVeKGsBA5L9lneDVZJaZ9Vc1yb8oX08x85857NmTYU75HeXLVZX7zUVpJ38Sut+ws585oyJ+fiXsvj0SoxJrPNws/xqtRXzcJTeLvmrTEmj2fTmoW98fb1zfDfbFbvnNXnHb/5wKtpO2H5dMjfF00dgx3xtvm83wXU+DdcgbdiTF7Lmf4csKdZWD0NcEPxG5nXW8hX9rrUYj+CFlTz2yw9YnQGXnj5fE7avOPdrikQN21mjEnpR3KXWfg//O7sSrydEPwuDLyN7oYm1vNBWdo8jc3Mez9nWmldB+DVOXlehMWdD8wsbIlXcX0db688wyx8J8bk9jTdlWbhj3ink23wO/YjzcL4GJN9crewdF6q0dzjT61ZX7nm9tmFeFtWnvllaSs5rk0prSPv2OZ9xwb8Lv7YZtZZHqQrXXdL2vp4tFqMySlm4Tf4efk1vAPR8WbhghiTnwCYhVF4B6HH8BqYl/Eb5hXxY53XF6ap71yLfVFJupr/hlvQ1DWmPK8N+Hn2nZy0JeW1Anm/t2pU89sEr/HZFS8sPYTXgH2C16gdQwfs+6RAXKEYk0fMwk14W9GlMSaP4FWUjcAqmaDdlP/iVSwb5MzbsMrszEw/51WwXQDStqXHYHFP1CeBn+GdiUppXsXb1K5Nq/huAkabhQvLSyAZL6SfG2f+Ltko/Wyp9Fit5m5cmlLaZ59WsM+qOa5NKe2LoTnz8qbNxGtN7osxWVThNjbKmVZad3aft2Z/tRtpr97LgMvSqsi7gRPS8/K/eAechXhP8MVBIe1d29aG4m2n5dM+xduPm9Imv+Fm9DYLa+eUijcE/pup7p2J9z2Y1tITDDVU8W/TLPTCg/BNMSY/LJsX2iZ7ba/D3TkU7Gz8B3YWQPpYxFRglFkYUZ7YLDRY+sxxWlV6F7ClWfhKWdLjqszHBLxN90yz0C1nuz1L7Sw57Tzg3fPn4o95YBa6m4Xu2QRpfkudivo0k5c78Av98WW9jvvjj9fMxi8YtfReC3nK8yR+J/9Ds7BMta1ZWMn8Ea6qjmszpuP7+XvZY5B2SvthTvob8U6BuSVis5A3sMC+ZuFzmTSr4CWCT/EepSXv4RfiQku31UrP46WqmdMq9FJ1cKkK8lP8HFwhs2wDcEodsnlCdr+ahWF4B7d7WwhkNf0NV+jEsm18Ay8YTMpMvhHfj+fmraCJ83B5VfzbZEmNRUNZmv54bUmHpBJxFWJMnjcLv8cvgF+LMXkYOAyvsn7ILNyIn1Qr4G10e+An9hnpKk7Bq5b+ZBZ+hf+YdsFLQlBhySXG5D9m4TC89PpcWlKfna7nS3jni43wjkWnmIUd8QvzS/gJvBt+J1zqifpF4EGzcDv+g5iP39Ufli6T+9xrmpd/mj9qcUK6D8bjbUyH4o9l7JvTXru8pgEHmYWz8YvyImByLHsOuCyfjWZhf7zt+29pdeff8d6o6wOj8LbI69NFqjmuedv71Cwcg19wHzML1+DVZ9/H21/XLVvkEsCAX5iF7dN8vpOm24G0xFe2zL+Av6Sdv97FqxO3AM6OMcm2JU/DSxG/Mu9J/Cle8q7oWehKmIVS0Cvd0G2SmfZQjMlDmbTX48/gLvUsc47t8EdSbsP7UbyHd4I7GPhLjEmpb8UfgL2A+9JjtTL+G+i+zBprbyBwt1m4A3+M6Ui82eL45hZqg99wS+bhN5YDgAfwDleH423BZ2Ty9Qfz522PTG8qpqTLfg5/7HJ9qut/0KJqfpsxJu+ahXuA/czCB3gP9YHAD/B9s9x9GszCkfiz2uDn0sDMufzXGJPJmbRn4J3MlmvceJWIq/dz/MJfKhW/jF8cLsHbbi7ES84B72W4uLdmeuH4Oj7YxdFpunks6THdUrvjYjEm16XrehI/CS/Hnyvtjz9XV6qCmoS3Pe6NP6f7M/wu+hCW3CG/jD8+sCl+s/Ar/EJwDfCVbHVfE3n5CR54V8N7Zh6Pd1LaPsZkaqXfqQo/xavjjsDbcW9hyc1Mc/l8Cu/M81t84JLL8O87Ag/A92bSVnxcm9neH/C29nfwi91ReND4SU7aj/GbsqPT73Im/uzqt/Fq5rwSymX4M8kHpJ+98UFRTitLNxY/vt/EbyBuIb9ae3mcnf4rPce5WWba9mVpe+A3nU21jZb8FX9SYVv893ZJ+vc5+A0tADEmv2fJjd8v8ZvCf2bTtKGd8GB2Jl4bMR3YJsakyfGMS2r8G27JAnzfrYr/Rg/G22O/mjZJZfP1ffycWoQfz8vwG6f3WHJ8a6qa3ybece03+M1I6Vr1U5bt7d5aP2bJubsK3lu+9P+9ytKWRhF7ZXk22NDY2KGbjzoFW/Iw+0kxJue1lF66NmtHb2+qlvkoWP/FH3n5btH5aa1SqT7GpN1X95vesNVmzMIM4N0Yk21aTNwMlYjrrLw9KG1fOiH9b6x/jkTqajhe5fjTojMisjzMwmfxkc2q7eOzDLUR199TZuE+vKppdbx65WvA+BiT6YXmTKSNpb3v69F2K9Km0j4WNRkCVoG4/v6IB9/98f3/Et4etMz4wyIi0vmpjVhERKRAaiMWEREpkAKxiIhIgRSIRURECqRALCIiUiD1mhapUDr276/wISc/i48MNS7GZGyR+RKRjk0lYpHKrYQPO7gjsCbwLeAks/DtQnMlIh2aHl+Sqizv8IodeXjGPOkA9e/FmBxVdF5EpGNS1XQHZRaquYMaHGMyq63y0lGlryR8i6VfqfYO/sKAi9KXCTS3/ErAV6n8DTiV5GkF/MUPP8AHm5+Lv2DitObeLpWznj7AyfiA+J/D3870TLqehzPpNgBOA4YBA/C3zfwbfw3kL8pfCJC+Bu9M/AUVa+E1BLcDp8eYvJVJ90V8cP4dgfXwF4K8ANwKjG3pu6Sv5fx7ug/GxZgc2do8p8usgb90Y3S6zg/xt1ddDdwQY9KYpjsDf5tOUz6JMVm5fGKl+7vS79iW627FMa/4WLblsenMFIg7rv3L/v81/A00V7Psawvn1nC7DwHdgI8LWr6WhuFBeDz+urcG4PP4G3BuMQsfxZhMbGb5S4G38Tca1crF+EXpdvyNT0PT/29mFkKMyaKWVmAWBuKvulsD+DV+UesJbAKsU5b8c/jbfm7HX8v5Cf4avkOBfczCpqXXJaZj6/4Fv8BehQeD/8FfGfl1s5B9U9f38bdj3QH8Dj/e2+FvDtrbLIyIMWnubWNnAXnv4a0qz2m+V8DfBf5l4Ab8zT7d8Qv/dfg+Lr0RayLwfM42N8HfKja5fEaV+7vS79iW665q/1HdsWzLY9NpKRB3UDEmv83+Py2dHQo8Wj4vj1lYEVi1pVcc5mx3Ef5u3FZZ3uVrbFj6eXOMyR2liWbhUfzdqPviF+ZlmIUL8dLw9jEmH9UiM2ZhY/wmYGKMyV6Z6S/hQX8f4OYKVvVb/Le9SV4JJCvG5F6WfsVcaZsP4SXxA1lS4j8Zf/frd2JMbsmkfSTN17H4xRn8dY/nxpi8nVntlWZhJv7Ch4Pwjm/LSN+DOwZ/GcqFy5lngK3wYzU2xuSYTPrL8dd1/oD0Yp++vnCZVxiahavSP3+dk+WK93dmfc1+x7Zcdyv2X8XHsi2PTWemQNwFmIUD8btLw1/ufSD+wvlDgOvNQg/8ZDe86qkH/o7iPwBnZYN1XhtvZv074MHtMPzOeDbw8xiTG2q1fGY9g/CLjOHvtn0Av/jcD8yKMdm2gl0zPP18smz6C+lnz7yFzMLYNK/bx5jMq2A7lRqNl8rHlk2/Bn+H7H60EIjNwtfxC9tRMSavmoWVgZWrveHC9z34O45LtsPfmV1eZT8efz/s90gDcYzJE02sdzx+8f6fJvK/Iv59/4TfBDUXpCrJM3jHOoA52YkxJh+ZhXn4O3qblFbz7oO/c/ZPZfOq3t+Vfse2XHcTcvdfa49lJetmOY9NZ6FA3LX8Em+zuYYlbaHgVVwHA7fhF/pPgG3wO+rNqPwF6+fg1c5X4e08h+GB/vkYkz/Xanmz8Bm8+n0t4ErgObxq/n78jVaVGgbMjTF5uWz6runnI+ULmIVL8RfdbxdjskyVf1rV1qeKPLyZqW7eAn8Z+2PZBDEmC83CU+n8loxMP/9tFiYDOwMrpqWXs5qqLTELq+HVn6sBG7HkJSRTM8lWBRaWt9nFmCwyCx8AXzALfVu4Oflc+vl6E/OPATZk2RewtzbP4PvzLeAEszALr17vht+QDgd+2MKm9sYDxqUxJp+WzWvN/q70O7bluqvZf01p8ljW8dh0CgrEXUs3YLOcO+oXgc/HmGTbbceZhbOBU8zCljEmj9GyVYEtSlW1ZuEP6bqPBCoJxJUu/xP8IrBfjMnv0mlXmIUL8Ha8FqUdRL4IPGwWSm1p/YDd8c46/6SsNJG21/0Iv0l4ySyUZj0cY7Jz+ve6+Bu1KjUYmJX+PQCYF2PyYU66V4Avm4VVWqgK3yD9vAaYCXwX36/HAjeZhZVjTK7LWe5gvH2uZBa+f7P9Df4ObJC28z1VmmgWNmVJSWddIDcQp6W10/AbvWVK9mZhMN4R7KwYk1lprUdzKskzMSbzzcLuwLV49WjJu8BeMSaTWtjOQXity29y5lW1v6v8jm25bqhw/+Vp6VhWuu4aHJtOQYG4a7kir1ore2FP25p74O/ZTIBT8HacSgLx5dl1xZi8Yhb+BQypMH+VLr8bPpjGLWXTf0mFgRjYFH+OfhuW7sz2CXARcF5ZmxgxJrNZuod1ntfw6vJKvZb5uzse5PMszKRpLhD3SD/fxUvtpZua2/GbmnPMwg05nb4m4W1ya+C1ILvjNyZZY/GeuxPMwhi8s9bG6fSP8dqW5t41PBYYAZwcY/LPnPlX4DcxFzWzjmrzXPJemt878JqOPngHpJvNwh4xJjFvobQX8FeBe2NM8m6wqt3f1XzHtlw3VLf/yo2l+WNZzbpbdWw6EwXiruVfTc0wC4fj1UAbs+xAL+XtOk15MWfaG3gHn1ouPxh4rDyYxJj81yy8VeG2Su3DJwLT8ZLG1/Dq+K1jTOZXuJ6lxJgsxG9gWuN9fMSuPKtl0jSn1Hv1lrKbmvlm4Q7gALyk9Vx2oRiT/+C9XAEmmYXbgMfNQrcYk3PTNA+bhX3wjmN3pmk/xUszfwe+gTd5LCOtXTkSuLq0vrL5pcdjvl5WM9OkSvKcrvtL+AX+mBiTKzPTb8EDwDVmYb2camfw0jDpd8xT8f5uxXdsy3VXvP/KtXQsq1n3ch6bTkOBuGvJvYibhWPxath78IvsHLzUtQ5wPZWPwNbUj6WlUmStlq9Gqcf079KLBsCd5s9sHmIWdkh7gFYlrbKrtFQB3kZd+t5zgI3Mwqo51dPr4NXWLfXQLn2X13LmlXrdtnhjFWPyN7PwJHA4cG5m+q1mYSL+SEoP4J/pDdBjeG3CMo/+mD+bewreIW+ZNj/zoUMvwtsPXzML66ezSo/n9EynzYuZZ5UrzTPebroa/txrNv37ZuFOPKgMYkknvVK+VsKD3Zv44zh5KtrfrfyObbnuZTSz/xZr6Vi2Yt2tOjadjQKxgD+TPAvYOVvKNAs7FZaj5s0C1jcLK5Tl97NArwrXMRx4IxOES67Ge5OPJucxjAp8nta3ET+Ol2q2JPMseNrxZVP8GeyWPIZfID+XM6807b858/J0I6fjWXrj8FQmf2vj1Y8Pljd9mIXT8Tb3G4GDyzt6ZbbTDx8kZJec+ful/47Hmx+qzXMpIK2Yk36lss+s3fAOgZc00W4Ple/v1nzHtlx3U3KPOVR8LKtdd2uPTaeisaYFvCTaSKbkmZYGTiwsR82bjA8aMLps+o8rWdgsdMN7lj5VPi99VOMVYPe0dFutUhtxpf+ypZ3x+HEYU7bOQ/C2199lJ5qFlc3ChmZh3czkSXib4n5ph7RS2v54++7MGJPnM9PXzvsSZmE7/LGUac192bSX+KX4hfTnZfNOA84AbsIfV2tqMJIF+Ljd5f8OT+f/Kf3/Ha3M87Pp54Fl6XsBewDzyS9xlaql854dLplEZfu7qu/YlutuzTGv9FjW8dh0Kp3+TkMq8ge8uuiutNpxTeA7tI/Rr/Kcj+fvOrOwJd4p5KvAV/Aeuy3dqW+KB46nmpg/FQ9+X6GyUuhiy9NGHGPytFkYBxyZHoepLBlZ60GW7Z26Dt7W+yCwbbqO+Wbhx/gjYNPMx8JeBX8UbBW8qi/rivTCfh/+rOdqeG3BPngQOK6UMA0Gj+HVtC/hz1mPTtP/NMbk/kzaI/AevP9O98d3Mr3MAV4vdcJJ2zT/UL4/Mr1+X4gxyc6vOM+psXgV83lpm+Sf8ZLZIfgN3RExJp+UbXsAsBPeF+Hp8ryVVLq/W/Ed23LdVe2/ao5lteumFcemM1IgFoBf4KXhg4BL8FLaeLwd6NlmlitEjMk8s/BVvF37+3jgvR8fcOJxlnRyaUqpffipJuZPwS8E36DKQFwDY/Cq6kPxasZ5+GMgpzVTolxKjMnV5oMhnACcjT+b/Cg+Ilb5Y2S34I/F7I9XbzbiF9Cr8LGB/51J+xE+6tR38Ivk+/j+3inG5O6y9ZaeeV4XH7qw3INAa3vDVpNnYkxmpzdsp+EDseyDnyNPAcfF/GFMD8Rv1prqpJVdfzX7uypttO6q9h/VHct6HJtOR29fkk7DfKCPecBVMSZdYiAAEen41EYsHVLazluuNCZtp3/uUEQ6D1VNS0d1l1mYDTyBVyHugA9N+QjeyUVEpENQIJaOajLeyWNP/LGI/+Btxmd29of/RaRzURuxiIhIgdRGLCIiUiAFYhERkQIpEIuIiBRIgVhERKRACsQiIiIFUiAWEREpkAKxiIhIgTSgRzvS0NDwEv7mo1kFZ0VEpCMZBLzT2Ng4uOiMtIYCcfuyZrdu3foMHTo098XcIiKyrOeee44PPmjppWvtlwJx+zJr6NChfaZPn150PkREOozhw4czY8aMWUXno7XURiwiIlIglYhFRGpszpw5TJg4hdfnzmetfr3Ze9SuDBgwoOhsSTulErGISA1NmjyVE8+9lpcXDWalQdvz8qLBnHjutUyaPLXorEk7pUAsIlIjc+bMYeI9TzBw2M5079ELgO49ejFw2M5MvOcJXn311WIzKO2SArGISI1MmDiFfkO2zp3Xd/0RTLhtSp1zJB2BArGISI28Pnf+4pJwudXX7M1rc9+sb4akQ1AgFmmHHn300aKzIK2wVr/evP/uW7nzFrwzn7X7aYgAWZYCsUg7dNpppxadBWmFvUftytyZ+TdR856fxt577VrnHElHoEAsIlIjAwYMYNSOmzN7xl0seGc+4CXh2TPuYtSOm9O/f/+CcyjtkZ4jFhGpoT13G8lWm2/GhNum8NqsJxnYrw/Hn3yIgrA0SYFYpB0aM2ZM0VmQ5dC/f3+OPvKQorMhHYSqpkXaoV12UVuiSFehQCzSDpmForMgInWiQCwiIlIgBWIREZECKRCLtEMjRowoOgsiUicKxCLt0Nln/6zoLIhInSgQi7RDp556StFZEJE6USAWaYemTZtWdBZEpE4UiEVERAqkQCwiIlIgBWKRdijGpOgsiEidKBCLtEN33jml6CyISJ0oEIu0Q2PHji06CyJSJwrEIiIiBeowr0E0CycBw4DhwGBgdozJoAqXPRwYl/63X4zJvLL5KwBHAz8ABgFzgQnAaTEmC3LWtwFwPrANsAowAzg9xuS+qr+YiIh0aR2pRHwOsD3wAjC/0oXMwgDgXOC9ZpJdDFwEPAv8CLgVOAqYnAbp7PrWAx4BtgYuAI4H1gDuNgt6ZY7UxFlnnV10FkSkTjpMiRhYL8bkRQCz8Awe/CoxDngReAbYr3ymWdgYD74TY0z2ykx/CbgU2Ae4ObPIuUAvYHiMyVNp2huBvwPjzMKGMSaNVX0zkTJDhgwpOgsiUicdpkRcCsLVMAvfAHbHq5w/bSLZaKABGFs2/RrgfTLB2yysnq7vgVIQTvP2HnAt8EVgi2rzKVJu9Oh9is6CiNRJhwnE1TILawK/Aq6KMXmsmaRbAIuApdLEmCwEnmLpwLoJsCrwaM56SmMSKhCLiEjFOlLVdLXOx280Tmoh3QBgXozJhznzXgG+bBZWiTH5KE1bmp6XFmCdljLW0NCwG7Bbzqx133777ZYWFxGRTqRTBmKz8GW8OnrfGJOWIlt3IC8IAyzMpPko/aSJ9Nm0zWpsbJwMTC6f3tDQMLxnz559W1peOr+RI0cWnQURqZNOVzVtFlbB23eTGJNbKljkfby6Oc9qmTTZz7z05WlFWu2YY44tOgsiUiedLhADRwAbAheZhfVL/4Ae6fzBZuELmfRzgL5mIS+4roNXW3+USVuanpcW8qutRapy+OGHFZ0FEamTzlg1PRC/wbirifmPAQtY8vjT48COwJbAw6VEZmE1YFPgocyyT+PV0lvnrHdE+vlEK/MtstjMmTOLzoKI1ElnLBFfB3wr598D6fzvs/TzxOOBRmBM2XoOwdt7f1eakD6mNBnY1iz8b2m6WVgDOBiYSVnvaxERkeZ0mBKxWdgfL+0C9ANWMQunpP+fHWNyE0CMyV+Bv+Ysv2v65+TsEJcxJk+bhXHAkWZhIjAVGIqPrPUgSw/mAd4LewfgHrNwMfAOHrTXAXbRYB5SC336fKboLIhInXSYQAwchI/tnFUaB/BB4KblWPcYYBZwKLALMA+4DB9relE2YYzJ82bhK8B5wIksGWt6pxgTvURWamL8+PFFZ0FE6qShsVEFuPaioaFh+rBhw4ZNnz696KxIwW688QYOOOC7RWdDpEMYPnw4M2bMmNHY2Di86Ly0RmdsIxbp8G66aXkqeESkI1EgFhERKZACsYiISIEUiEXaoXHjLi86CyJSJwrEIiIiBVIgFmmHjjji8KKzICJ1okAsIiJSIAViERGRAikQi7RD+++/f9FZEJE6USAWaYc0qpZI16FALNIOffvb3y46CyJSJwrEIu3Qm2++UXQWRKROFIhFREQKpEAs0g4NGTKk6CyISJ0oEIu0Q5dffkXRWRCROlEgFmmHLr74oqKzICJ1okAs0g5NnTq16CyISJ0oEIuIiBRopaIzICJLLDgqADBp6JK/Rbqa1S9Nis5CXalELCIiUiAFYhERkQIpEIuIiBRIbcQi7UipbcwsEGPXaicT6apUIhYRESmQArFIOzRmzJiisyAidVLTQGwWvm4W+jUzv69Z+HottynSGe2yy65FZ0FE6qTWJeL7AWtm/g5pGhFphpmeIRbpKmodiBtamL8isKjG2xQREemw2qKNuLGZeV8G5rXBNkVERDqk5X58ySwcDRydmTTWLPw8J2lvYE3gN8u7TZHObsSIEUVnQUTqpBbPEb8FzE7/HgS8AbxelqYReAaYBoytwTZFOrWzz/5Z0VkQkTpZ7kAcY3IDcAOAWXgJODHG5I7lXa9IV3bqqacoGIt0ETUdWSvGZHAt1yfSVU2bNq3oLIhInbTZEJdmoTvwGXJ6UseY/LuttisiItKR1DQQm4UVgBOAHwFrN5N0xVpuV0REpKOqdYn4PODHwN+B2/COWyJSJb3wQaTrqHUg3g/4U4zJyBqvV6RLufPOKRrmUqSLqHUg7g38scbrBMAsnAQMA4YDg4HZMSaDmkh7HLAbsAHQB3gT+AdwaYzJ7TnpV8Cfhf4B/gjWXGACcFqMyYKc9BsA5wPbAKsAM4DTY0zuW64vKZIaO3asArFIF1HrkbWeBvrXeJ0l5wDbAy8A81tIuyUwC7gYOAy4EOgOTDQLp+akvxi4CHgWb9++FTgKmJwG6cXMwnrAI8DWwAXA8cAawN1mQQMEi4hIVWpdIj4T+LVZ+HWMycs1Xvd6MSYvApiFZ/DglyvG5Nvl08zCWGA6cIJZOCfG5NN0+sZ48J0YY7JXJv1LwKXAPsDNmVWdC/QChseYPJWmvRFvFx9nFjaMMWlumE8REcmYM2cOEyZO4fW581mrX2/2HrUrAwYMKDpbdVPrQDwcH2XrWbNwO/AS8GlZmsYYk7OrXXEpCLdWjMknZuEV4EvAypl8jcYfsRpbtsg1eOez/UgDsVlYHdgdeKAUhNN1v2cWrgXOArYAHluevIqcdVbVPxGRDmnS5KlMvOcJ+g3Zmu6DNuPld9/ixHOvZdSOm7Pnbl2ju1GtA/EZmb/3ayJNI1CXq4xZ6IM/KtUX+BawE3B/jMnCTLIt8DdCLRU8Y0wWmoWn0vklmwCrAo/mbK40AoMCsSy3IUOGFJ0FkTY3Z84cJt7zBAOH7bx4WvcevRg4bGcm3nMXW22+Gf37t1VrZ/tR6zbiwRX8+0KNt9mcfwH/xdt+T8UfqdqnLM0AYF6MyYc5y78C9DULq2TSlqbnpQVYZ7lyLAKMHl1+mop0PhMmTqHfkK1z5/VdfwQTbptS5xwVo9ZDXM5uOVVdjQJWw4Pjt4Bu+Bug5mbSdAfygjDAwkyaj9JPmkifTdushoaG3fBe3eXWffvtt1taXESkU3h97ny6D9osd97qa/bmtVlP1jlHxWjLIS7XB9YCnokxKSS6xJg8lPnvdWbhFuD/zMJGMSalntfvA59tYhWrZdJkP1etIG2TGhsbJwOTy6c3NDQM79mzZ9+WlhcR6QzW6tebl999i+49ei0zb8E78xnYr0/9M1WAWldNYxZ2NQsvAP8EHsI7cGEWPmsWnjcL36z1NqtwAz705qjMtDl49XNecF0Hr7b+KJO2ND0vLeRXW4tUZeTIrtFJRbq2vUftytyZeV1uYN7z09h7r67xLH1NA7FZ2Ba4HR9A40wyL3yIMfkv/gxwkY1f3dLP7G3W4/h+2DKb0CysBmwKPJGZ/DReLZ3XqFF6k/sTOfNEqnLMMccWnQWRNjdgwABG7bg5s2fcxYJ3vJJywTvzmT3jLkbtuHmX6KgFtS8Rnwb8FdgKGJcz/1F8dKw2YxZWNwvLPGNsFlYEjkj/m33H3Hi8J/eYskUOwdt7f1eaEGPyHl6lvK1Z+N/MutcADgZmoh7TUgOHH35Y0VkQqYs9dxvJ+ScfwsAVZ/PJrPsYuOJszj/5kC7z6BLUvo14c3yox0VmuYNM/Yfm38rUJLOwPzAw/W8/YBWzcEr6/9kxJjelfw8BHjQLf8Crx9/Eq41H40Ne3hBj8nBpvTEmT5uFccCRZmEiMBUYio+s9SBLD+YBcBKwA3CPWbgYeAcP2usAu2gwD6mFmTNnFp0Fkbrp378/Rx95SNHZKEytA/GKNN0DGfx53o+amd+cg/CxnbNKzyM/CJQC8X+A3wJfBb4B9ADeBp5M05cHVvDS8CzgUGAXYB5wGT7W9KJswhiT583CV/DBPk5kyVjTO8WY6JU50il19ZGPRNpSrQPxc8DXgMubmL8rXnVdtRiTbStMN48lVdCVrvtTfDzqCytM/xywRzXbEKlGnz6fKToLi2nkI5G2Ves24l8D3zQLB2XW3WgWupuFS/FOTlfXeJsinc748eOLzgKw9MhHpUdMlox89ASvvvpqsRkU6QRqGohjTK7AOz9dg3dcagRuwauGjwSujzH5XdNrEBGAG2+8oegsABr5SKQeahaIzUI3s3AA3rY6CrgXfwfwm3gHqG/FmBxUq+2JdGY33XRTy4nq4PW583MHW4B05KO5b9Y3QyKdUC3biD8ErgWOijG5EphUw3WLSAE08pFI26tZiTjtXfxvfCxnEekENPKRSNurdWetG4D9mxguUkQqNG5cUw8e1JdGPhJpe7V+fOkRvH34KbNwOd5ha5mXIJS9jEFE2rE9dxvJVptvxoTbpvDarCcZ2K8Px598iIKwSI3UOhDHzN+X4L2msxrSaSvWeLsincoRRxxOjO1nfJiuPvKRSFuqdSD+Xo3XJyIi0qnVNBDHmLSPhx9FREQ6iJq/j1hElt/+++9fdBZEpE4UiEXaoQMO+G7RWRCROlEgFmmHvv3tbxedBRGpEwVikXbozTffKDoLIlInCsQiIiIFUiAWaYeGDBlSdBZEpE4UiEXaocsvv6LoLIhInSgQi7RDF198UdFZEJE6USAWaYemTp1adBZEpE4UiEVERAqkQCwiIlIgBWKRduiWW35fdBZEpE4UiEXaoZkzZxadBRGpEwVikXbotNNOLToLIlInCsQiIiIFUiAWEREpkAKxSDs0ZsyYorMgInWiQCzSDu2yy65FZ0FE6kSBWKQdMgtFZ0FE6kSBWEREpEAKxCIiIgVSIBZph0aMGFF0FkSkThSIRdqhs8/+WdFZEJE6USAWaYdOPfWUorMgInWiQCzSDk2bNq3oLIhInSgQi4iIFEiBWEREpEArFZ2BSpmFk4BhwHBgMDA7xmRQTroGYF9gV2BzYAAwD3gK+HmMyV9yllkBOBr4ATAImAtMAE6LMVmQk34D4HxgG2AVYAZweozJfcv5NUUAiDEpOgsiUicdqUR8DrA98AIwv5l0qwI3ARsAvwd+BFyNB/FHzcJ+OctcDFwEPJumvxU4CpicBunFzMJ6wCPA1sAFwPHAGsDdZkHDIUlN3HnnlKKzICJ10mFKxMB6MSYvApiFZ/Dgl+cTYNsYkwezE83CNcDfgQvNws0xJovS6RvjwXdijMlemfQvAZcC+wA3Z1Z1LtALGB5j8lSa9sZ03ePMwoYxJo3L+V2ljc2ZM4cJE6fw+tz5rNWvN3uP2pUBAwYUna3Fxo4dq/GmRbqIDlMiLgXhCtJ9Uh6E0+mvAw8Cn03/lYwGGoCxZYtcA7wPLC5Bm4XVgd2BB0pBOF33e8C1wBeBLSrJpxRn0uSpnHjutby8aDArDdqelxcN5sRzr2XS5KlFZ01EuqAOE4hr5HPAR8BbmWlbAIuAx7IJY0wW4u3K2cC6CV71/WjOukvPmygQt2Nz5sxh4j1PMHDYznTv0QuA7j16MXDYzky85wleffXVYjMoIl1OlwnEZmEksCUwPg2yJQOAeTEmH+Ys9grQ1yyskklbmp6XFmCdWuRX2saEiVPoN2Tr3Hl91x/BhNvaR9vsWWedXXQWRKROOlIbcauZhSF4B65XgOPKZncH8oIwwMJMmo/ST5pIn03brIaGht2A3XJmrfv222+3tLgsh9fnzqf7oM1y562+Zm9em/VknXOUb8iQIUVnQUTqpNMHYrMwGLgXaAR2jjGZW5bkfZZuM85aLZMm+7lqBWmb1NjYOBmYXD69oaFheM+ePfu2tLy03lr9evPyu28trpbOWvDOfAb261P/TOUYPXofPcIk0kV06qppszAIuB/vYW0xJk/nJJuDVz/nBdd18GrrjzJpS9Pz0kJ+tbW0E3uP2pW5M/Oa+GHe89PYey/1VBaR+uq0gdgsDMSDcE88CDdV5/g4vh+2LFt+NWBT4InM5Kfxaum8RsbSe+ueyJkn7cSAAQMYtePmzJ5xFwve8cfRF7wzn9kz7mLUjpvTv3//gnMoIl1NpwzEaRB+AOgN7BhjMr2Z5OPxausxZdMPwdt7f1eakD6mNBnY1iz8b2Z7awAHAzMp630t7c+eu43k/JMPYeCKs/lk1n0MXHE25598CHvuNrLorC02cmT7yYuItK2GxsaOMfaEWdgfGJj+90f40JIXpv+fHWNyU5quB/BXfBjMy8gPjDF9rri07suAI4HbganAUHxkrT8D25cG/0jTrp+u82N8RK538KD9JWCXGJO7W/sdGxoapg8bNmzY9OnN3TeIiEjW8OHDmTFjxozGxsbhReelNTpSZ62D8LGds0rPeDyI94oG+AwehMEDdp7tgNcz/x8DzAIOBXbBx6a+DB9relF2wRiT583CV4DzgBNZMtb0TjEm6l0jNXH44Ydx+eVXFJ0NEamDDlMi7gpUIpYSs6Be0yIVUolY2oUFR+l9E53JpKF+TFe/VMFYpLPrlJ21REREOgoFYhERkQIpEIuIiBRIbcSdhNoSOxd11hLpOlQiFhERKZACsYiISIEUiEXaoXHjLi86CyJSJ2oj7iTmzJnDhIlTeH3ufNbq15u9R+3KgAEDis6WiIi0QCXiTmDS5KmceO61vLxoMCsN2p6XFw3mxHOvZdLkqUVnTVrpiCMOLzoLIlInCsQd3Jw5c5h4zxMMHLbz4pfdd+/Ri4HDdmbiPU/w6quvFptBERFplgJxBzdh4hT6Dcl7PTL0XX8EE26bUucciYhINRSIO7jX585fXBIut/qavXlt7pv1zZDUxP777190FkSkThSIO7i1+vXm/Xffyp234J35rN2vT30zJDVxwAHfLToLIlInCsQd3N6jdmXuzEdz5817fhp777VrnXMkIiLVUCDu4AYMGMCoHTdn9oy7WPDOfMBLwrNn3MWoHTenf//+BedQRESao+eIO4E9dxvJVptvxoTbpvDarCcZ2K8Px598iIKwiEgHoEDcSfTv35+jjzyk6GyIiEiVVDUtIiJSoIbGxsai8yCphoaGN7p169Zn6NChRWdFRKTDeO655/jggw/ebGxs/EzReWkNBeJ2pKGh4SVgTWDWcqymJ/B2TTLUNWh/VUf7qzraX9Vp7f4aBLzT2Ng4uLbZqQ8F4k6moaHh6sbGxkOLzkdHof1VHe2v6mh/Vaer7i+1EYuIiBRIgVhERKRACsQiIiIFUiAWEREpkAKxiIhIgRSIO5/JRWegg9H+qo72V3W0v6rTJfeXHl8SEREpkErEIiIiBVIgFhERKZACsYiISIEUiEVERAqkQCwiIlIgBWIREZECrVR0BmRpZuEM4PRmknwSY7JyBWmPjzH5Zdm6VwCOBn6AvzZsLjABOC3GZMFyZbxAZmEN4ChgNP69PgT+BVwN3BBj0phJuwFwPrANsAowAzg9xuS+nPV26f2l88uZhbWAM4FdgLWA14Db8fPmrbK0Or8q3F86v5ZQibj9mQjsn/PvF+n8vAfej8lJf2dOuouBi4BngR8Bt+IX5MnpSd7hpPm+CzgbeBw4DvgZsCJwHXBeJu16wCPA1sAFwPHAGsDdZiHkrL5L76+Mrnx+fRb4C/B9YBL+vf4IHAbcbxa6Z9Lq/Kpif2V02fOrRCXidibG5G/A38qnm4Wr0j9/nbPYpBiTWc2t1yxsjJ+8E2NM9spMfwm4FNgHuLmV2S7SVsBXgbExJseUJpqFy4F/4HfPP0knnwv0AobHmDyVprsR+DswzixsmCkNan8t0ZXPr5OBgcB3YkxuKU00C4/g3+dY/EYGdH5BdfurpCufX4BKxB1Cehe5D/AK8Kcm0qxpFpq7sRoNNABjy6ZfA7wP7Lf8OS3EmunnnOzEGJOPgHnAAgCzsDqwO/BA6SKZpnsPuBb4IrBFZhVden+V68Ln13bAB8Dvy6aPBxYC3wOdXxkV7a9yXfj8AhSIO4q98QvodTEmn+bM/xvwNrDQLDxiFnbOSbMFsAh4LDsxxmQh8BRLXyQ6kseAt4ATzMK3zMK6ZmEDs3AuMBw4I023CbAq8GjOOqaln9l90NX3V1ZXPr9WBRZm+xkAxJgswgPOF8xCX3R+lVS6v7K68vkFKBB3FAcBjcBvyqa/hXew+RGwB3ASXi10p1k4sCztAGBejMmHOet/BehrFlapYZ7rIsZkPl4SeRPvuDEbr2I9AtgrxuSaNOmA9POVnNWUpq2TmdbV9xfo/AKvVu5tFjbNTkz/3zv977ro/CqpdH+Bzq/F1EbczqW9ML8K3Btj8lJ2XozJ2Jz0vwGeAS42C39Iq8YAuuO9Y/MszKT5qBb5rrP38O98B95Zpg8eWG42C3vEmET8u0H+Psh+fzJ/d+X9pfPLjQX2BCaYhTH4d984nf4xsDL+vXR+ubFUtr90fmWoRNz+HZR+XltJ4hiTN4Ar8U4jX87Meh+vNsqzWiZNh2IWvoQHkxhjcnyMye0xJr/Gb15eA64xCyuy5Lvl7YO879/V91eurnZ+xZg8jPfP6IH35J2NP7lwPzAlTfYOOr+AqvZXU8t3qfOrRIG4HUs7LxyAVyPeXsWis9LPbFvMHLz6Ju9kXgev9umId5PH4D/EW7MTY0zexy8EA/FnDkudk7LVg5RNy1YrdvX91ZxZ6WdXOL+IMbkV+BywGfB1YECMyQ/TaZ8Az6Pza7EK91dzZqWfXeL8AlVNt3e74Q/EX9JE20hThqSfr2emPQ7sCGwJPFyaaBZWAzYFHlqunBandJHLK8WtlPl8Gq/a2jon3Yj084nMtK6+v5rTlc4vANJOkk+V/m8W1sYDzYMxJu+bBZ1fGS3trxYW73Lnl0rE7VupWnqZZ4fNwkpmoWfO9M/jD8+/gVdBlozHO3yNKVvkELxt5Xc1yG8Rnk0/D8xONAu98A4g84EX0ramycC2ZuF/M+nWAA4GZrJ0j8wuvb90fjUtHTziUvxm5uew+DElnV858vaXzq+lNTQ2NracSurOLAwA/g1MjzHZKmd+L+AlfPSa5/AL6Ab4j34NYHRaRZRd5jLgSLyaeyowFB+Z5s/A9ukjBh2KWRiIDyPYG/8x/hnvfHQIXsV6RIzJ5Wna9fGL4cf4KD3vpOm+BOwSY3J32bq77P7S+eXSQPoY/p1eAnriz7QOB34aY3JOJq3Orwr3l86vpalquv06EL+DbKqT1gfAbfhISXviJ+88IAEuiDF5LGeZMXj7y6H4OLDzgMvwsVo75EkcYzLbLGwJnAbsgHcU+QCvFjsuxmRiJu3zZuEr+DCOJ7JkLOCdYkySnNWPoevuL51f7iP8OdfvAP3xDkGP4+fMUoFV5xdQ+f7S+ZWhErGIiEiB1EYsIiJSIAViERGRAikQi4iIFEiBWEREpEAKxCIiIgVSIBYRESmQArGIiEiBFIhFREQKpEAsIiJSIAViERGRAikQi4iIFEgvfRCRXGZhO+BcYGN8UP7vxZhcX2imRDohBWIRWYZZ6A1MBP4DHIe/ReeRZhdavu31wt+u80CMyQNttR2R9kiBWETybAH0Ag7KvkqyDfUCTk//fqAO2xNpN9RGLCJ51k4/3yw0FyJdgN5HLNIJmIXV8JfRjwY+j7+g/WXgTzEmx6dpVgB+gr9YvT8wE3+J/RC8NDo4xmSWWZgFDCzfRoxJQ7qeVfHq6n2B9YCFwMP4C9qfLMtXA/BD4GBgKPAp8ARwVozJ/WmabYH7c77W7BiTQa3ZHyIdiUrEIp3DODyYTgOOBX4K3Atsn0lzEXAO8G/gBOCP6XK7l61rDHB1+vc5wP7pP8zCysCf0m09ChyDB/ONgD+bhc3L1nUT8Cvg+XSbZwA9gWgWStt9Ll0PwO2Z7Y2p4vuLdFgqEYt0AmbhTWBajMnIJuZvgAe8+4EdY0w+TacPw0uoDaQl4nT6gcB1wHbZzlNm4Rg8oO8UY3J3ZvqawDPAizEm26bTvoF3+PpBjMnVmbQr4TcMnwG+EGPSaBYGAS8BZ8aYnLF8e0OkY1FnLZHO4W1gY7PwPzEmz+TM3wMPtheVgjBAjMkMsxCBHSvczn7AP4DpZqFv2bwIfNcsdIsx+SBN+y4wKSftZLx0PAT4V4XbFumUFIhFOocxeDXw02bhRbzkOxmYHGOyCPhCmu4fOcs+S+WBeCjQDZjbTJq+ePv0UKAH8HozaddCgVi6OAVikU4gxuSPafXuSGAbIAAHAQ+bhYCXhgHy2qIacqY1pQF4Gm+HbsrcTNq5wHeaSZtXehfpUhSIRTqJGJM3gd8Cv017K5+Hd5DaA3ghTTYUeLFs0aFVbGYm0A+4Ly1pt5T2i3jb9XstpFVnFemy1GtapIMzCyumI1MtFmPSCJQeJeoD3IEHu2PNwoqZZYfhpedK3Yg/Y5xbIjYLa5WlXQEfJrOltKVA3aeKvIh0CioRi3R8PYBXzcIdePD9LzAYOAyYj7cTzzEL44AjgfvMwm3AZ9P//xXYrMJtXQIY8AuzsD1wH/AOsC6wA/5M8XYAMSZ/MAvXAUemAX8KMA/4HLA1sD5p23WMyRtm4XlgH7PwAt6uvCDGZHLrd4tIx6ASsUjH9z4wFg++xwNX4M/h3gFsFWMyJ013NHAKMAj4BbAncESariIxJh8Du6Tr6gecCVwMfBuv8j63LP33gQOARcBJwGXAd/ES8Ellq98Xr84+B7glTSvS6ek5YpEuziycQWZkrWJzI9L1qEQsIiJSIAViERGRAikQi4iIFEhtxCIiIgVSiVhERKRACsQiIiIFUiAWEREpkAKxiIhIgRSIRURECqRALCIiUiAFYhERkQIpEIuIiBRIgVhERKRACsQiIiIFUiAWEREpkAKxiIhIgRSIRURECvT/AcaYGSdL8WV6AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 216x108 with 1 Axes>"
      ]
     },
     "metadata": {
      "image/png": {
       "height": 150,
       "width": 241
      },
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "X, y = df.sqfeet.values.reshape(-1,1), df.rent.values\n",
    "t = DecisionTreeRegressor(max_depth=1)\n",
    "t.fit(X,y)\n",
    "\n",
    "fig, ax = plt.subplots(1, 1, figsize=(3,1.5))\n",
    "t = rtreeviz_univar(t,\n",
    "                    X, y,\n",
    "                    feature_names='sqfeet',\n",
    "                    target_name='rent',\n",
    "                    fontsize=9,\n",
    "                    colors={'scatter_edge': 'black'},\n",
    "                    ax=ax)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of picking the optimal split point, we can choose a random value in between the minimum and maximum x value, like extremely random forests do:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stumpfit(x, y):\n",
    "    if len(x)==1 or len(np.unique(x))==1: # if one x value, make leaf\n",
    "        return TreeNode(prediction=y[0])\n",
    "    split = np.round(np.random.uniform(min(x),max(x)))\n",
    "    t = TreeNode(split)\n",
    "    t.left = TreeNode(prediction=np.mean(y[x<split]))\n",
    "    t.right = TreeNode(prediction=np.mean(y[x>=split]))\n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Run the following code multiple times to see how it creates different y lists in the nodes, according to the split value.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.49.1 (20210923.0004)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"215pt\" height=\"174pt\"\n",
       " viewBox=\"0.00 0.00 215.00 174.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 170)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-170 211,-170 211,4 -4,4\"/>\n",
       "<!-- node140573082159136 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140573082159136</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"146,-166 52,-166 52,-94 146,-94 146,-166\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-150 54,-164 144,-164 144,-150 54,-150\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"54,-150 144,-150 \"/>\n",
       "<text text-anchor=\"start\" x=\"77.5\" y=\"-154.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-148 54,-150 144,-150 144,-148 54,-148\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-134 54,-148 107,-148 107,-134 54,-134\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-134 107,-148 \"/>\n",
       "<text text-anchor=\"start\" x=\"83\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-134 107,-148 144,-148 144,-134 107,-134\"/>\n",
       "<text text-anchor=\"start\" x=\"108\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;782.0&#39;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-132 54,-134 144,-134 144,-132 54,-132\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-118 54,-132 107,-132 107,-118 54,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-118 107,-132 \"/>\n",
       "<text text-anchor=\"start\" x=\"55\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-118 107,-132 144,-132 144,-118 107,-118\"/>\n",
       "<text text-anchor=\"start\" x=\"108\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"54,-115 144,-115 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-113 54,-115 144,-115 144,-113 54,-113\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-104 54,-113 107,-113 107,-104 54,-104\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-104 107,-113 \"/>\n",
       "<text text-anchor=\"start\" x=\"55\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-104 107,-113 107,-113 107,-104 107,-104\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-104 107,-113 144,-113 144,-104 107,-104\"/>\n",
       "<text text-anchor=\"start\" x=\"131\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-101 54,-104 107,-104 107,-101 54,-101\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-101 107,-104 \"/>\n",
       "<text text-anchor=\"start\" x=\"80\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-101 107,-104 107,-104 107,-101 107,-101\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-101 107,-104 144,-104 144,-101 107,-101\"/>\n",
       "<text text-anchor=\"start\" x=\"125\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"54,-96 54,-101 107,-101 107,-96 54,-96\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"107,-96 107,-101 \"/>\n",
       "<text text-anchor=\"start\" x=\"80\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-96 107,-101 107,-101 107,-96 107,-96\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"107,-96 107,-101 144,-101 144,-96 107,-96\"/>\n",
       "<text text-anchor=\"start\" x=\"125\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082158896 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>node140573082158896</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"100,-72 0,-72 0,0 100,0 100,-72\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-56 2,-70 98,-70 98,-56 2,-56\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-56 98,-56 \"/>\n",
       "<text text-anchor=\"start\" x=\"28.5\" y=\"-60.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-54 2,-56 98,-56 98,-54 2,-54\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-40 2,-54 55,-54 55,-40 2,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-40 55,-54 \"/>\n",
       "<text text-anchor=\"start\" x=\"31\" y=\"-44.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-40 55,-54 98,-54 98,-40 55,-40\"/>\n",
       "<text text-anchor=\"start\" x=\"56\" y=\"-44.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-38 2,-40 98,-40 98,-38 2,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-24 2,-38 55,-38 55,-24 2,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-24 55,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-24 55,-38 98,-38 98,-24 55,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"56\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1160.0&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-21 98,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-19 2,-21 98,-21 98,-19 2,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-10 2,-19 55,-19 55,-10 2,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-10 55,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-10 55,-19 55,-19 55,-10 55,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-10 55,-19 98,-19 98,-10 55,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"85\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-7 2,-10 55,-10 55,-7 2,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-7 55,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"28\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-7 55,-10 55,-10 55,-7 55,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-7 55,-10 98,-10 98,-7 55,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"76\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-2 2,-7 55,-7 55,-2 2,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-2 55,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"28\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-2 55,-7 55,-7 55,-2 55,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-2 55,-7 98,-7 98,-2 55,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"76\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082159136&#45;&gt;node140573082158896 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>node140573082159136:c&#45;&gt;node140573082158896</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M78.6,-98C76.6,-93.75 72.72,-85.46 68.43,-76.33\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"79.32\" cy=\"-99.55\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"69.54,-75.4 66.58,-72.37 67.01,-76.59 69.54,-75.4\"/>\n",
       "</g>\n",
       "<!-- node140573082159760 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>node140573082159760</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"207,-72 107,-72 107,0 207,0 207,-72\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-56 109,-70 205,-70 205,-56 109,-56\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"109,-56 205,-56 \"/>\n",
       "<text text-anchor=\"start\" x=\"135.5\" y=\"-60.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-54 109,-56 205,-56 205,-54 109,-54\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-40 109,-54 162,-54 162,-40 109,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"162,-40 162,-54 \"/>\n",
       "<text text-anchor=\"start\" x=\"138\" y=\"-44.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"162,-40 162,-54 205,-54 205,-40 162,-40\"/>\n",
       "<text text-anchor=\"start\" x=\"163\" y=\"-44.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-38 109,-40 205,-40 205,-38 109,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-24 109,-38 162,-38 162,-24 109,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"162,-24 162,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"110\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"162,-24 162,-38 205,-38 205,-24 162,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"163\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1307.5&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"109,-21 205,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-19 109,-21 205,-21 205,-19 109,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-10 109,-19 162,-19 162,-10 109,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"162,-10 162,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"110\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"162,-10 162,-19 162,-19 162,-10 162,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"162,-10 162,-19 205,-19 205,-10 162,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"192\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-7 109,-10 162,-10 162,-7 109,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"162,-7 162,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"135\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"162,-7 162,-10 162,-10 162,-7 162,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"162,-7 162,-10 205,-10 205,-7 162,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"183\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"109,-2 109,-7 162,-7 162,-2 109,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"162,-2 162,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"135\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"162,-2 162,-7 162,-7 162,-2 162,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"162,-2 162,-7 205,-7 205,-2 162,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"183\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082159136&#45;&gt;node140573082159760 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>node140573082159136:c&#45;&gt;node140573082159760</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M127.45,-98C129.51,-93.75 133.53,-85.46 137.95,-76.33\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"126.7\" cy=\"-99.56\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"139.38,-76.58 139.87,-72.37 136.86,-75.36 139.38,-76.58\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fd9b8a08460>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root = stumpfit(X.reshape(-1),y)\n",
    "treeviz(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating random decision trees (single variable)\n",
    "\n",
    "And now to demonstrate the magic of recursion. If we replace\n",
    "\n",
    "```\n",
    "t.left = TreeNode(prediction=np.mean(y[x<split]))\n",
    "```\n",
    "\n",
    "with\n",
    "\n",
    "```\n",
    "t.left  = treefit(x[x<split],  y[x<split])\n",
    "```\n",
    "\n",
    "(and same for `t.right`) then all of the sudden we get a full decision tree, rather than just a stump!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def treefit(x, y):\n",
    "    if len(x)==1 or len(np.unique(x))==1: # if one x value, make leaf\n",
    "        return TreeNode(prediction=y[0])\n",
    "    split = np.round(np.random.uniform(min(x),max(x)))\n",
    "    t = TreeNode(split)\n",
    "    t.left  = treefit(x[x<split],  y[x<split])\n",
    "    t.right = treefit(x[x>=split], y[x>=split])\n",
    "    return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.49.1 (20210923.0004)\n",
       " -->\n",
       "<!-- Title: G Pages: 1 -->\n",
       "<svg width=\"440pt\" height=\"362pt\"\n",
       " viewBox=\"0.00 0.00 439.50 362.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 358)\">\n",
       "<title>G</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-358 435.5,-358 435.5,4 -4,4\"/>\n",
       "<!-- node140573082211856 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>node140573082211856</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"278,-354 184,-354 184,-282 278,-282 278,-354\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-338 186,-352 276,-352 276,-338 186,-338\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"186,-338 276,-338 \"/>\n",
       "<text text-anchor=\"start\" x=\"209.5\" y=\"-342.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-336 186,-338 276,-338 276,-336 186,-336\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-322 186,-336 239,-336 239,-322 186,-322\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"239,-322 239,-336 \"/>\n",
       "<text text-anchor=\"start\" x=\"215\" y=\"-326.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"239,-322 239,-336 276,-336 276,-322 239,-322\"/>\n",
       "<text text-anchor=\"start\" x=\"240\" y=\"-326.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;878.0&#39;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-320 186,-322 276,-322 276,-320 186,-320\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-306 186,-320 239,-320 239,-306 186,-306\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"239,-306 239,-320 \"/>\n",
       "<text text-anchor=\"start\" x=\"187\" y=\"-310.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"239,-306 239,-320 276,-320 276,-306 239,-306\"/>\n",
       "<text text-anchor=\"start\" x=\"240\" y=\"-310.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"186,-303 276,-303 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-301 186,-303 276,-303 276,-301 186,-301\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-292 186,-301 239,-301 239,-292 186,-292\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"239,-292 239,-301 \"/>\n",
       "<text text-anchor=\"start\" x=\"187\" y=\"-295.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"239,-292 239,-301 239,-301 239,-292 239,-292\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"239,-292 239,-301 276,-301 276,-292 239,-292\"/>\n",
       "<text text-anchor=\"start\" x=\"263\" y=\"-295.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-289 186,-292 239,-292 239,-289 186,-289\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"239,-289 239,-292 \"/>\n",
       "<text text-anchor=\"start\" x=\"212\" y=\"-290.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"239,-289 239,-292 239,-292 239,-289 239,-289\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"239,-289 239,-292 276,-292 276,-289 239,-289\"/>\n",
       "<text text-anchor=\"start\" x=\"257\" y=\"-290.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"186,-284 186,-289 239,-289 239,-284 186,-284\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"239,-284 239,-289 \"/>\n",
       "<text text-anchor=\"start\" x=\"212\" y=\"-285.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"239,-284 239,-289 239,-289 239,-284 239,-284\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"239,-284 239,-289 276,-289 276,-284 239,-284\"/>\n",
       "<text text-anchor=\"start\" x=\"257\" y=\"-285.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211760 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>node140573082211760</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"210,-260 116,-260 116,-188 210,-188 210,-260\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-244 118,-258 208,-258 208,-244 118,-244\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"118,-244 208,-244 \"/>\n",
       "<text text-anchor=\"start\" x=\"141.5\" y=\"-248.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-242 118,-244 208,-244 208,-242 118,-242\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-228 118,-242 171,-242 171,-228 118,-228\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"171,-228 171,-242 \"/>\n",
       "<text text-anchor=\"start\" x=\"147\" y=\"-232.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"171,-228 171,-242 208,-242 208,-228 171,-228\"/>\n",
       "<text text-anchor=\"start\" x=\"172\" y=\"-232.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;836.0&#39;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-226 118,-228 208,-228 208,-226 118,-226\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-212 118,-226 171,-226 171,-212 118,-212\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"171,-212 171,-226 \"/>\n",
       "<text text-anchor=\"start\" x=\"119\" y=\"-216.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"171,-212 171,-226 208,-226 208,-212 171,-212\"/>\n",
       "<text text-anchor=\"start\" x=\"172\" y=\"-216.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"118,-209 208,-209 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-207 118,-209 208,-209 208,-207 118,-207\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-198 118,-207 171,-207 171,-198 118,-198\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"171,-198 171,-207 \"/>\n",
       "<text text-anchor=\"start\" x=\"119\" y=\"-201.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"171,-198 171,-207 171,-207 171,-198 171,-198\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"171,-198 171,-207 208,-207 208,-198 171,-198\"/>\n",
       "<text text-anchor=\"start\" x=\"195\" y=\"-201.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-195 118,-198 171,-198 171,-195 118,-195\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"171,-195 171,-198 \"/>\n",
       "<text text-anchor=\"start\" x=\"144\" y=\"-196.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"171,-195 171,-198 171,-198 171,-195 171,-195\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"171,-195 171,-198 208,-198 208,-195 171,-195\"/>\n",
       "<text text-anchor=\"start\" x=\"189\" y=\"-196.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"118,-190 118,-195 171,-195 171,-190 118,-190\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"171,-190 171,-195 \"/>\n",
       "<text text-anchor=\"start\" x=\"144\" y=\"-191.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"171,-190 171,-195 171,-195 171,-190 171,-190\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"171,-190 171,-195 208,-195 208,-190 171,-190\"/>\n",
       "<text text-anchor=\"start\" x=\"189\" y=\"-191.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211856&#45;&gt;node140573082211760 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>node140573082211856:c&#45;&gt;node140573082211760</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M209.94,-286.31C206.69,-282.06 199.97,-273.28 192.6,-263.66\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"211.03\" cy=\"-287.73\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"193.62,-262.69 190.08,-260.37 191.4,-264.4 193.62,-262.69\"/>\n",
       "</g>\n",
       "<!-- node140573082211376 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>node140573082211376</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"354,-260 260,-260 260,-188 354,-188 354,-260\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-244 262,-258 352,-258 352,-244 262,-244\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"262,-244 352,-244 \"/>\n",
       "<text text-anchor=\"start\" x=\"285.5\" y=\"-248.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-242 262,-244 352,-244 352,-242 262,-242\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-228 262,-242 315,-242 315,-228 262,-228\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"315,-228 315,-242 \"/>\n",
       "<text text-anchor=\"start\" x=\"291\" y=\"-232.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"315,-228 315,-242 352,-242 352,-228 315,-228\"/>\n",
       "<text text-anchor=\"start\" x=\"316\" y=\"-232.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;943.0&#39;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-226 262,-228 352,-228 352,-226 262,-226\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-212 262,-226 315,-226 315,-212 262,-212\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"315,-212 315,-226 \"/>\n",
       "<text text-anchor=\"start\" x=\"263\" y=\"-216.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"315,-212 315,-226 352,-226 352,-212 315,-212\"/>\n",
       "<text text-anchor=\"start\" x=\"316\" y=\"-216.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"262,-209 352,-209 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-207 262,-209 352,-209 352,-207 262,-207\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-198 262,-207 315,-207 315,-198 262,-198\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"315,-198 315,-207 \"/>\n",
       "<text text-anchor=\"start\" x=\"263\" y=\"-201.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"315,-198 315,-207 315,-207 315,-198 315,-198\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"315,-198 315,-207 352,-207 352,-198 315,-198\"/>\n",
       "<text text-anchor=\"start\" x=\"339\" y=\"-201.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-195 262,-198 315,-198 315,-195 262,-195\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"315,-195 315,-198 \"/>\n",
       "<text text-anchor=\"start\" x=\"288\" y=\"-196.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"315,-195 315,-198 315,-198 315,-195 315,-195\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"315,-195 315,-198 352,-198 352,-195 315,-195\"/>\n",
       "<text text-anchor=\"start\" x=\"333\" y=\"-196.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"262,-190 262,-195 315,-195 315,-190 262,-190\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"315,-190 315,-195 \"/>\n",
       "<text text-anchor=\"start\" x=\"288\" y=\"-191.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"315,-190 315,-195 315,-195 315,-190 315,-190\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"315,-190 315,-195 352,-195 352,-190 315,-190\"/>\n",
       "<text text-anchor=\"start\" x=\"333\" y=\"-191.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211856&#45;&gt;node140573082211376 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>node140573082211856:c&#45;&gt;node140573082211376</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M260.06,-286.31C263.31,-282.06 270.03,-273.28 277.4,-263.66\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"258.97\" cy=\"-287.73\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"278.6,-264.4 279.92,-260.37 276.38,-262.69 278.6,-264.4\"/>\n",
       "</g>\n",
       "<!-- node140573082211904 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>node140573082211904</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"137,-166 43,-166 43,-94 137,-94 137,-166\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-150 45,-164 135,-164 135,-150 45,-150\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"45,-150 135,-150 \"/>\n",
       "<text text-anchor=\"start\" x=\"68.5\" y=\"-154.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-148 45,-150 135,-150 135,-148 45,-148\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-134 45,-148 98,-148 98,-134 45,-134\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"98,-134 98,-148 \"/>\n",
       "<text text-anchor=\"start\" x=\"74\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"98,-134 98,-148 135,-148 135,-134 98,-134\"/>\n",
       "<text text-anchor=\"start\" x=\"99\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;791.0&#39;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-132 45,-134 135,-134 135,-132 45,-132\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-118 45,-132 98,-132 98,-118 45,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"98,-118 98,-132 \"/>\n",
       "<text text-anchor=\"start\" x=\"46\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"98,-118 98,-132 135,-132 135,-118 98,-118\"/>\n",
       "<text text-anchor=\"start\" x=\"99\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"45,-115 135,-115 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-113 45,-115 135,-115 135,-113 45,-113\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-104 45,-113 98,-113 98,-104 45,-104\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"98,-104 98,-113 \"/>\n",
       "<text text-anchor=\"start\" x=\"46\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"98,-104 98,-113 98,-113 98,-104 98,-104\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"98,-104 98,-113 135,-113 135,-104 98,-104\"/>\n",
       "<text text-anchor=\"start\" x=\"122\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-101 45,-104 98,-104 98,-101 45,-101\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"98,-101 98,-104 \"/>\n",
       "<text text-anchor=\"start\" x=\"71\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"98,-101 98,-104 98,-104 98,-101 98,-101\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"98,-101 98,-104 135,-104 135,-101 98,-101\"/>\n",
       "<text text-anchor=\"start\" x=\"116\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"45,-96 45,-101 98,-101 98,-96 45,-96\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"98,-96 98,-101 \"/>\n",
       "<text text-anchor=\"start\" x=\"71\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"98,-96 98,-101 98,-101 98,-96 98,-96\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"98,-96 98,-101 135,-101 135,-96 98,-96\"/>\n",
       "<text text-anchor=\"start\" x=\"116\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211760&#45;&gt;node140573082211904 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>node140573082211760:c&#45;&gt;node140573082211904</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M141.73,-192.31C138.15,-188.06 130.74,-179.28 122.62,-169.66\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"142.97\" cy=\"-193.78\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"123.49,-168.52 119.84,-166.37 121.35,-170.33 123.49,-168.52\"/>\n",
       "</g>\n",
       "<!-- node140573082212048 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>node140573082212048</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"235.5,-166 144.5,-166 144.5,-94 235.5,-94 235.5,-166\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-150 147,-164 234,-164 234,-150 147,-150\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"147,-150 234,-150 \"/>\n",
       "<text text-anchor=\"start\" x=\"169\" y=\"-154.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-148 147,-150 234,-150 234,-148 147,-148\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-134 147,-148 200,-148 200,-134 147,-134\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"200,-134 200,-148 \"/>\n",
       "<text text-anchor=\"start\" x=\"176\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"200,-134 200,-148 234,-148 234,-134 200,-134\"/>\n",
       "<text text-anchor=\"start\" x=\"201\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-132 147,-134 234,-134 234,-132 147,-132\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-118 147,-132 200,-132 200,-118 147,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"200,-118 200,-132 \"/>\n",
       "<text text-anchor=\"start\" x=\"148\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"200,-118 200,-132 234,-132 234,-118 200,-118\"/>\n",
       "<text text-anchor=\"start\" x=\"201\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1280&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"147,-115 234,-115 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-113 147,-115 234,-115 234,-113 147,-113\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-104 147,-113 200,-113 200,-104 147,-104\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"200,-104 200,-113 \"/>\n",
       "<text text-anchor=\"start\" x=\"148\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"200,-104 200,-113 200,-113 200,-104 200,-104\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"200,-104 200,-113 234,-113 234,-104 200,-104\"/>\n",
       "<text text-anchor=\"start\" x=\"221\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-101 147,-104 200,-104 200,-101 147,-101\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"200,-101 200,-104 \"/>\n",
       "<text text-anchor=\"start\" x=\"173\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"200,-101 200,-104 200,-104 200,-101 200,-101\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"200,-101 200,-104 234,-104 234,-101 200,-101\"/>\n",
       "<text text-anchor=\"start\" x=\"216.5\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"147,-96 147,-101 200,-101 200,-96 147,-96\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"200,-96 200,-101 \"/>\n",
       "<text text-anchor=\"start\" x=\"173\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"200,-96 200,-101 200,-101 200,-96 200,-96\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"200,-96 200,-101 234,-101 234,-96 200,-96\"/>\n",
       "<text text-anchor=\"start\" x=\"216.5\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211760&#45;&gt;node140573082212048 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>node140573082211760:c&#45;&gt;node140573082212048</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M190,-191.68C190,-187.4 190,-179.47 190,-170.72\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"190\" cy=\"-193.4\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"191.4,-170.37 190,-166.37 188.6,-170.37 191.4,-170.37\"/>\n",
       "</g>\n",
       "<!-- node140573082211568 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>node140573082211568</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"90,-72 0,-72 0,0 90,0 90,-72\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-56 2,-70 88,-70 88,-56 2,-56\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-56 88,-56 \"/>\n",
       "<text text-anchor=\"start\" x=\"23.5\" y=\"-60.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-54 2,-56 88,-56 88,-54 2,-54\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-40 2,-54 55,-54 55,-40 2,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-40 55,-54 \"/>\n",
       "<text text-anchor=\"start\" x=\"31\" y=\"-44.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-40 55,-54 88,-54 88,-40 55,-40\"/>\n",
       "<text text-anchor=\"start\" x=\"56\" y=\"-44.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-38 2,-40 88,-40 88,-38 2,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-24 2,-38 55,-38 55,-24 2,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-24 55,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-24 55,-38 88,-38 88,-24 55,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"56\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1160&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"2,-21 88,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-19 2,-21 88,-21 88,-19 2,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-10 2,-19 55,-19 55,-10 2,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-10 55,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"3\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-10 55,-19 55,-19 55,-10 55,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-10 55,-19 88,-19 88,-10 55,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"75\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-7 2,-10 55,-10 55,-7 2,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-7 55,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"28\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-7 55,-10 55,-10 55,-7 55,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-7 55,-10 88,-10 88,-7 55,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"71\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"2,-2 2,-7 55,-7 55,-2 2,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"55,-2 55,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"28\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-2 55,-7 55,-7 55,-2 55,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"55,-2 55,-7 88,-7 88,-2 55,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"71\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211904&#45;&gt;node140573082211568 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>node140573082211904:c&#45;&gt;node140573082211568</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M69.78,-98C68.06,-93.75 64.69,-85.46 60.98,-76.33\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"70.4\" cy=\"-99.52\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"62.17,-75.55 59.37,-72.37 59.58,-76.6 62.17,-75.55\"/>\n",
       "</g>\n",
       "<!-- node140573082212000 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>node140573082212000</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"188.5,-72 97.5,-72 97.5,0 188.5,0 188.5,-72\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-56 100,-70 187,-70 187,-56 100,-56\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"100,-56 187,-56 \"/>\n",
       "<text text-anchor=\"start\" x=\"122\" y=\"-60.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-54 100,-56 187,-56 187,-54 100,-54\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-40 100,-54 153,-54 153,-40 100,-40\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"153,-40 153,-54 \"/>\n",
       "<text text-anchor=\"start\" x=\"129\" y=\"-44.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"153,-40 153,-54 187,-54 187,-40 153,-40\"/>\n",
       "<text text-anchor=\"start\" x=\"154\" y=\"-44.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-38 100,-40 187,-40 187,-38 100,-38\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-24 100,-38 153,-38 153,-24 100,-24\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"153,-24 153,-38 \"/>\n",
       "<text text-anchor=\"start\" x=\"101\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"153,-24 153,-38 187,-38 187,-24 153,-24\"/>\n",
       "<text text-anchor=\"start\" x=\"154\" y=\"-28.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1200&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"100,-21 187,-21 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-19 100,-21 187,-21 187,-19 100,-19\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-10 100,-19 153,-19 153,-10 100,-10\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"153,-10 153,-19 \"/>\n",
       "<text text-anchor=\"start\" x=\"101\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"153,-10 153,-19 153,-19 153,-10 153,-10\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"153,-10 153,-19 187,-19 187,-10 153,-10\"/>\n",
       "<text text-anchor=\"start\" x=\"174\" y=\"-13.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-7 100,-10 153,-10 153,-7 100,-7\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"153,-7 153,-10 \"/>\n",
       "<text text-anchor=\"start\" x=\"126\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"153,-7 153,-10 153,-10 153,-7 153,-7\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"153,-7 153,-10 187,-10 187,-7 153,-7\"/>\n",
       "<text text-anchor=\"start\" x=\"169.5\" y=\"-8.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"100,-2 100,-7 153,-7 153,-2 100,-2\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"153,-2 153,-7 \"/>\n",
       "<text text-anchor=\"start\" x=\"126\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"153,-2 153,-7 153,-7 153,-2 153,-2\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"153,-2 153,-7 187,-7 187,-2 153,-2\"/>\n",
       "<text text-anchor=\"start\" x=\"169.5\" y=\"-3.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211904&#45;&gt;node140573082212000 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>node140573082211904:c&#45;&gt;node140573082212000</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M118.22,-98C119.94,-93.75 123.31,-85.46 127.02,-76.33\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"117.6\" cy=\"-99.52\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"128.42,-76.6 128.63,-72.37 125.83,-75.55 128.42,-76.6\"/>\n",
       "</g>\n",
       "<!-- node140573082211952 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>node140573082211952</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"333.5,-166 242.5,-166 242.5,-94 333.5,-94 333.5,-166\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-150 245,-164 332,-164 332,-150 245,-150\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"245,-150 332,-150 \"/>\n",
       "<text text-anchor=\"start\" x=\"267\" y=\"-154.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-148 245,-150 332,-150 332,-148 245,-148\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-134 245,-148 298,-148 298,-134 245,-134\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"298,-134 298,-148 \"/>\n",
       "<text text-anchor=\"start\" x=\"274\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"298,-134 298,-148 332,-148 332,-134 298,-134\"/>\n",
       "<text text-anchor=\"start\" x=\"299\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-132 245,-134 332,-134 332,-132 245,-132\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-118 245,-132 298,-132 298,-118 245,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"298,-118 298,-132 \"/>\n",
       "<text text-anchor=\"start\" x=\"246\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"298,-118 298,-132 332,-132 332,-118 298,-118\"/>\n",
       "<text text-anchor=\"start\" x=\"299\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1450&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"245,-115 332,-115 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-113 245,-115 332,-115 332,-113 245,-113\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-104 245,-113 298,-113 298,-104 245,-104\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"298,-104 298,-113 \"/>\n",
       "<text text-anchor=\"start\" x=\"246\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"298,-104 298,-113 298,-113 298,-104 298,-104\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"298,-104 298,-113 332,-113 332,-104 298,-104\"/>\n",
       "<text text-anchor=\"start\" x=\"319\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-101 245,-104 298,-104 298,-101 245,-101\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"298,-101 298,-104 \"/>\n",
       "<text text-anchor=\"start\" x=\"271\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"298,-101 298,-104 298,-104 298,-101 298,-101\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"298,-101 298,-104 332,-104 332,-101 298,-101\"/>\n",
       "<text text-anchor=\"start\" x=\"314.5\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"245,-96 245,-101 298,-101 298,-96 245,-96\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"298,-96 298,-101 \"/>\n",
       "<text text-anchor=\"start\" x=\"271\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"298,-96 298,-101 298,-101 298,-96 298,-96\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"298,-96 298,-101 332,-101 332,-96 298,-96\"/>\n",
       "<text text-anchor=\"start\" x=\"314.5\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211376&#45;&gt;node140573082211952 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>node140573082211376:c&#45;&gt;node140573082211952</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M288,-191.68C288,-187.4 288,-179.47 288,-170.72\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"288\" cy=\"-193.4\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"289.4,-170.37 288,-166.37 286.6,-170.37 289.4,-170.37\"/>\n",
       "</g>\n",
       "<!-- node140573082212240 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>node140573082212240</title>\n",
       "<polygon fill=\"#fefecd\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"431.5,-166 340.5,-166 340.5,-94 431.5,-94 431.5,-166\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-150 343,-164 430,-164 430,-150 343,-150\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"343,-150 430,-150 \"/>\n",
       "<text text-anchor=\"start\" x=\"365\" y=\"-154.2\" font-family=\"Times,serif\" font-style=\"italic\" font-size=\"11.00\" fill=\"#444443\">TreeNode</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-148 343,-150 430,-150 430,-148 343,-148\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-134 343,-148 396,-148 396,-134 343,-134\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"396,-134 396,-148 \"/>\n",
       "<text text-anchor=\"start\" x=\"372\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">split </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"396,-134 396,-148 430,-148 430,-134 396,-134\"/>\n",
       "<text text-anchor=\"start\" x=\"397\" y=\"-138.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#160;&#160;&#160;</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-132 343,-134 430,-134 430,-132 343,-132\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-118 343,-132 396,-132 396,-118 343,-118\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"396,-118 396,-132 \"/>\n",
       "<text text-anchor=\"start\" x=\"344\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\">prediction </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"396,-118 396,-132 430,-132 430,-118 396,-118\"/>\n",
       "<text text-anchor=\"start\" x=\"397\" y=\"-122.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"11.00\" fill=\"#444443\"> &#39;1300&#39;</text>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"343,-115 430,-115 \"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-113 343,-115 430,-115 430,-113 343,-113\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-104 343,-113 396,-113 396,-104 343,-104\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"396,-104 396,-113 \"/>\n",
       "<text text-anchor=\"start\" x=\"344\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">left</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"396,-104 396,-113 396,-113 396,-104 396,-104\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"396,-104 396,-113 430,-113 430,-104 396,-104\"/>\n",
       "<text text-anchor=\"start\" x=\"417\" y=\"-107.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"6.00\" fill=\"#444443\">right</text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-101 343,-104 396,-104 396,-101 343,-101\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"396,-101 396,-104 \"/>\n",
       "<text text-anchor=\"start\" x=\"369\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"396,-101 396,-104 396,-104 396,-101 396,-101\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"396,-101 396,-104 430,-104 430,-101 396,-101\"/>\n",
       "<text text-anchor=\"start\" x=\"412.5\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"1.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"343,-96 343,-101 396,-101 396,-96 343,-96\"/>\n",
       "<polyline fill=\"none\" stroke=\"#444443\" points=\"396,-96 396,-101 \"/>\n",
       "<text text-anchor=\"start\" x=\"369\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"396,-96 396,-101 396,-101 396,-96 396,-96\"/>\n",
       "<polygon fill=\"#fefecd\" stroke=\"transparent\" points=\"396,-96 396,-101 430,-101 430,-96 396,-96\"/>\n",
       "<text text-anchor=\"start\" x=\"412.5\" y=\"-97.6\" font-family=\"Helvetica,sans-Serif\" font-size=\"3.00\" fill=\"#444443\"> </text>\n",
       "</g>\n",
       "<!-- node140573082211376&#45;&gt;node140573082212240 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>node140573082211376:c&#45;&gt;node140573082212240</title>\n",
       "<path fill=\"none\" stroke=\"#444443\" stroke-width=\"0.5\" d=\"M336.18,-192.31C339.63,-188.06 346.77,-179.28 354.59,-169.66\"/>\n",
       "<ellipse fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" cx=\"335.01\" cy=\"-193.76\" rx=\"1.6\" ry=\"1.6\"/>\n",
       "<polygon fill=\"#444443\" stroke=\"#444443\" stroke-width=\"0.5\" points=\"355.83,-170.36 357.26,-166.37 353.65,-168.59 355.83,-170.36\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x7fd9b8a150d0>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root = treefit(X.reshape(-1),y)\n",
    "treeviz(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can run that multiple times to see different tree layouts according to randomness."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q.** How would you modify `treefit()` so that it creates a typical decision tree rather than a randomized decision tree?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "<summary>Solution</summary>\n",
    "Instead of choosing a random split, we would pick the split value in $x$ that got the best average child $y$ purity/similarity. In other words, exhaustively test each $x$ value as candidate split point by computing the MSE for left and right $y$ subregions. The split point that gets the best weighted average for left and right MSE, is the optimal split point.\n",
    "</details>"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}