{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BST:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._left = None   ## is the left subtree\n",
    "        self._value = None\n",
    "        self._right = None  ## is the right subtree\n",
    "\n",
    "    def empty(self):\n",
    "        return self._value == None\n",
    "            \n",
    "    def minBST(self):\n",
    "        if self.empty():  #BASE Case if not found\n",
    "            return None\n",
    "        elif self._left == None:\n",
    "            return self._value\n",
    "        else:\n",
    "            return self._left.minBST()\n",
    "   \n",
    "    def maxBST(self): \n",
    "        if self.empty():  #BASE Case if not found\n",
    "            return None\n",
    "        elif self._right == None:\n",
    "            return self._value\n",
    "        else:\n",
    "            return self._right.maxBST()\n",
    "        \n",
    "    def member(self,x):\n",
    "        if self.empty():  #BASE Case if not found\n",
    "            return False\n",
    "        elif x < self._value:\n",
    "            return self._left.member(x)\n",
    "        elif x > self._value:\n",
    "            return self._right.member(x)\n",
    "        else:  # BASE Case if found\n",
    "            return True\n",
    "  \n",
    "    def height(self):\n",
    "        if self.empty():\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self._left.height(),self._right.height())\n",
    "  \n",
    "    def size(self):\n",
    "        if self.empty():  #BASE Case\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + self._left.size() + self._right.size()\n",
    "  \n",
    "    def insert(self,x):  # return a boolean; True if successful and False otherwise\n",
    "        if self.empty(): # BASE CASE\n",
    "            self._value = x\n",
    "            self._left = BST()  ## MOST CRITICAL PART OF CODE; should not be None; This is where\n",
    "                               ## a future insert will happen\n",
    "            self._right = BST() ## MOST CRITICAL PART OF CODE; should not be None\n",
    "        elif x < self._value:\n",
    "            return self._left.insert(x)\n",
    "        elif x > self._value:\n",
    "            return self._right.insert(x)\n",
    "        else: # item found BASE CASE\n",
    "            return False\n",
    "\n",
    "    def delete(self,x):\n",
    "        return self.delete_helper(x) != None\n",
    "    \n",
    "    def delete_helper(self,x):\n",
    "        if self.empty():\n",
    "            return None\n",
    "        elif x == self._value:\n",
    "            if self._right.empty():\n",
    "                return self._left\n",
    "            elif self._left.empty():\n",
    "                return self._right\n",
    "            else:\n",
    "                rmin = self._right.min()\n",
    "                self._value = rmin\n",
    "                self._right = self._right.delete_helper(rmin)\n",
    "                return self\n",
    "        elif x < self._value:\n",
    "            t = self._left.delete_helper(x)\n",
    "            if t == None:\n",
    "                return None\n",
    "            else:\n",
    "                self._left = t\n",
    "                return self\n",
    "        else:\n",
    "            t = self._right.delete_helper(x)\n",
    "            if t == None:\n",
    "                return None\n",
    "            else:\n",
    "                self._right = t\n",
    "                return self\n",
    "\n",
    "    def __str__(self):\n",
    "        return \"{ \" + self.str_helper().strip(', ') + \" }\"\n",
    "\n",
    "    def str_helper(self):\n",
    "        if self.empty():\n",
    "            return \"\"\n",
    "        else:\n",
    "            return self._left.str_helper()+str(self._value)+\", \"+self._right.str_helper() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "************************\n",
      "BST t3\n",
      "{ 16, 20, 34, 41, 47, 83, 88, 97, 99, 100, 105 }\n",
      "************************\n",
      "BST t4\n",
      "{ 16, 20, 34, 41, 47, 83, 88, 97, 99, 100, 105 }\n",
      "************************\n"
     ]
    }
   ],
   "source": [
    "def main():\n",
    "    #t1 = BST(BST(BST(),10,BST()), 20, BST(BST(),30,BST()))\n",
    "    #t2 = BST(BST(BST(BST(),10,BST()),20,BST(BST(),30,BST())), \\\n",
    "    #       40, \\\n",
    "    #       BST(BST(BST(),50,BST()),600,BST(BST(),70,BST())))\n",
    "\n",
    "    nums = [47,34,97,88,41,20,16,105,100,83,99,97]\n",
    "    \n",
    "    t3 = BST()\n",
    "    for x in nums:\n",
    "        t3.insert(x) \n",
    "\n",
    "    t4 = BST()\n",
    "    for x in nums[::-1]:\n",
    "        t4.insert(x) \n",
    "\n",
    "    print(\"************************\")\n",
    "    print(\"BST t3\")\n",
    "    print(t3)\n",
    "    print(\"************************\")\n",
    "    print(\"BST t4\")\n",
    "    print(t4)\n",
    "    print(\"************************\")\n",
    "\n",
    "main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2, 1]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1,2,3][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}