      "collapsed": false
     },
     "outputs": [],
     "source": [
      "def check_balance(root):\n",
      "    # TODO: Implement me\n",
      "    pass"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
 
</s> remove     "collapsed": false
 </s> add     "collapsed": true </s> remove     "def _check_balance(root):\n",
    "    if root is None:\n",
    "        return (True, 0, 0)\n",
    "    left_balanced, left_min_h, left_max_h = _check_balance(root.left)\n",
    "    right_balanced, right_min_h, right_max_h = _check_balance(root.right)\n",
    "    min_h = 1 + min(left_min_h, right_min_h)\n",
    "    max_h = 1 + max(left_max_h, right_max_h)\n",
    "    balanced = left_balanced and right_balanced and abs(max_h-min_h) <= 1\n",
    "    return (balanced, min_h, max_h)\n",
    "\n",
    "\n",
    "def check_balance(root):\n",
    "    if root is None:\n",
    "        raise Exception('No root node')\n",
    "    balanced, _, _ = _check_balance(root)\n",
    "    return balanced"
 </s> add     "class BstBalance(Bst):\n",
    "\n",
    "    def _check_height(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        left_height = self._check_height(node.left)\n",
    "        if left_height == -1:\n",
    "            return -1\n",
    "        right_height = self._check_height(node.right)\n",
    "        if right_height == -1:\n",
    "            return -1\n",
    "        diff = abs(left_height-right_height)\n",
    "        if diff > 1:\n",
    "            return -1\n",
    "        return 1 + max(left_height, right_height)\n",
    "\n",
    "    def check_balance(self):\n",
    "        if self.root is None:\n",
    "            raise Exception('No root node')\n",
    "        height = self._check_height(self.root)\n",
    "        return height != -1" </s> remove     "        node = Node(5)\n",
    "        assert_equal(check_balance(node), True)\n",
    "\n",
    "        insert(node, 3)\n",
    "        insert(node, 8)\n",
    "        insert(node, 1)\n",
    "        insert(node, 4)\n",
    "        assert_equal(check_balance(node), True)\n",
    "\n",
    "        node = Node(5)\n",
    "        insert(node, 3)\n",
    "        insert(node, 8)\n",
    "        insert(node, 9)\n",
    "        insert(node, 10)\n",
    "        assert_equal(check_balance(node), False)\n",
    "\n",
    "        node = Node(3)\n",
    "        insert(node, 2)\n",
    "        insert(node, 1)\n",
    "        insert(node, 5)\n",
    "        insert(node, 4)\n",
    "        insert(node, 6)\n",
    "        insert(node, 7)\n",
    "        assert_equal(check_balance(node), False)\n",
 </s> add     "        bst = BstBalance(Node(5))\n",
    "        assert_equal(bst.check_balance(), True)\n",
    "\n",
    "        bst.insert(3)\n",
    "        bst.insert(8)\n",
    "        bst.insert(1)\n",
    "        bst.insert(4)\n",
    "        assert_equal(bst.check_balance(), True)\n",
    "\n",
    "        bst = BstBalance(Node(5))\n",
    "        bst.insert(3)\n",
    "        bst.insert(8)\n",
    "        bst.insert(9)\n",
    "        bst.insert(10)\n",
    "        assert_equal(bst.check_balance(), False)\n",
    "\n",
    "        bst = BstBalance(Node(3))\n",
    "        bst.insert(2)\n",
    "        bst.insert(1)\n",
    "        bst.insert(5)\n",
    "        bst.insert(4)\n",
    "        bst.insert(6)\n",
    "        bst.insert(7)\n",
    "        assert_equal(bst.check_balance(), True)\n", </s> remove     "        node = Node(5)\n",
    "        assert_equal(check_balance(node), True)\n",
    "\n",
    "        insert(node, 3)\n",
    "        insert(node, 8)\n",
    "        insert(node, 1)\n",
    "        insert(node, 4)\n",
    "        assert_equal(check_balance(node), True)\n",
    "\n",
    "        node = Node(5)\n",
    "        insert(node, 3)\n",
    "        insert(node, 8)\n",
    "        insert(node, 9)\n",
    "        insert(node, 10)\n",
    "        assert_equal(check_balance(node), False)\n",
    "\n",
    "        node = Node(3)\n",
    "        insert(node, 2)\n",
    "        insert(node, 1)\n",
    "        insert(node, 5)\n",
    "        insert(node, 4)\n",
    "        insert(node, 6)\n",
    "        insert(node, 7)\n",
    "        assert_equal(check_balance(node), False)\n",
 </s> add     "        bst = BstBalance(Node(5))\n",
    "        assert_equal(bst.check_balance(), True)\n",
    "\n",
    "        bst.insert(3)\n",
    "        bst.insert(8)\n",
    "        bst.insert(1)\n",
    "        bst.insert(4)\n",
    "        assert_equal(bst.check_balance(), True)\n",
    "\n",
    "        bst = BstBalance(Node(5))\n",
    "        bst.insert(3)\n",
    "        bst.insert(8)\n",
    "        bst.insert(9)\n",
    "        bst.insert(10)\n",
    "        assert_equal(bst.check_balance(), False)\n",
    "\n",
    "        bst = BstBalance(Node(3))\n",
    "        bst.insert(2)\n",
    "        bst.insert(1)\n",
    "        bst.insert(5)\n",
    "        bst.insert(4)\n",
    "        bst.insert(6)\n",
    "        bst.insert(7)\n",
    "        assert_equal(bst.check_balance(), True)\n", </s> remove     "        check_balance(None)\n",
 </s> add     "        bst = BstBalance(None)\n",
    "        bst.check_balance()\n",
    "class BstBalance(Bst):\n",
    "\n",
    "    def check_balance(self):\n",
    "        # TODO: Implement me\n",
    "        pass"
      "collapsed": false
     },
     "outputs": [],
     "source": [
    "class BstBalance(Bst):\n",
    "\n",
    "    def check_balance(self):\n",
    "        # TODO: Implement me\n",
    "        pass"
    "class BstBalance(Bst):\n",
    "\n",
    "    def check_balance(self):\n",
    "        # TODO: Implement me\n",
    "        pass"
    "class BstBalance(Bst):\n",
    "\n",
    "    def check_balance(self):\n",
    "        # TODO: Implement me\n",
    "        pass"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
keep keep keep keep replace replace replace keep keep keep keep keep
 Move tree check balance to a class (#99) 
graphs_trees/check_balance/check_balance_challenge.ipynb