{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the code ot go along with the video explanation. Check out the video lecture for full details!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    \n",
    "    def __init__(self,key,val,left=None,right=None,parent=None):\n",
    "        self.key = key\n",
    "        self.payload = val\n",
    "        self.leftChild = left\n",
    "        self.rightChild = right\n",
    "        self.parent = parent\n",
    "\n",
    "    def hasLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def hasRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def isLeftChild(self):\n",
    "        return self.parent and self.parent.leftChild == self\n",
    "\n",
    "    def isRightChild(self):\n",
    "        return self.parent and self.parent.rightChild == self\n",
    "\n",
    "    def isRoot(self):\n",
    "        return not self.parent\n",
    "\n",
    "    def isLeaf(self):\n",
    "        return not (self.rightChild or self.leftChild)\n",
    "\n",
    "    def hasAnyChildren(self):\n",
    "        return self.rightChild or self.leftChild\n",
    "\n",
    "    def hasBothChildren(self):\n",
    "        return self.rightChild and self.leftChild\n",
    "\n",
    "    def replaceNodeData(self,key,value,lc,rc):\n",
    "        self.key = key\n",
    "        self.payload = value\n",
    "        self.leftChild = lc\n",
    "        self.rightChild = rc\n",
    "        if self.hasLeftChild():\n",
    "            self.leftChild.parent = self\n",
    "        if self.hasRightChild():\n",
    "            self.rightChild.parent = self\n",
    "\n",
    "\n",
    "class BinarySearchTree:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.size = 0\n",
    "\n",
    "    def length(self):\n",
    "        return self.size\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "\n",
    "    def put(self,key,val):\n",
    "        if self.root:\n",
    "            self._put(key,val,self.root)\n",
    "        else:\n",
    "            self.root = TreeNode(key,val)\n",
    "        self.size = self.size + 1\n",
    "\n",
    "    def _put(self,key,val,currentNode):\n",
    "        if key < currentNode.key:\n",
    "            if currentNode.hasLeftChild():\n",
    "                   self._put(key,val,currentNode.leftChild)\n",
    "            else:\n",
    "                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)\n",
    "        else:\n",
    "            if currentNode.hasRightChild():\n",
    "                   self._put(key,val,currentNode.rightChild)\n",
    "            else:\n",
    "                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)\n",
    "\n",
    "    def __setitem__(self,k,v):\n",
    "        self.put(k,v)\n",
    "\n",
    "    def get(self,key):\n",
    "        if self.root:\n",
    "            res = self._get(key,self.root)\n",
    "            if res:\n",
    "                \n",
    "                return res.payload\n",
    "            else:\n",
    "                return None\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def _get(self,key,currentNode):\n",
    "        \n",
    "        if not currentNode:\n",
    "            return None\n",
    "        elif currentNode.key == key:\n",
    "            return currentNode\n",
    "        elif key < currentNode.key:\n",
    "            return self._get(key,currentNode.leftChild)\n",
    "        else:\n",
    "            return self._get(key,currentNode.rightChild)\n",
    "\n",
    "    def __getitem__(self,key):\n",
    "        return self.get(key)\n",
    "\n",
    "    def __contains__(self,key):\n",
    "        if self._get(key,self.root):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def delete(self,key):\n",
    "        \n",
    "        if self.size > 1:\n",
    "            \n",
    "            nodeToRemove = self._get(key,self.root)\n",
    "            if nodeToRemove:\n",
    "                self.remove(nodeToRemove)\n",
    "                self.size = self.size-1\n",
    "            else:\n",
    "                raise KeyError('Error, key not in tree')\n",
    "        elif self.size == 1 and self.root.key == key:\n",
    "            self.root = None\n",
    "            self.size = self.size - 1\n",
    "        else:\n",
    "            raise KeyError('Error, key not in tree')\n",
    "\n",
    "    def __delitem__(self,key):\n",
    "        \n",
    "        self.delete(key)\n",
    "\n",
    "    def spliceOut(self):\n",
    "        if self.isLeaf():\n",
    "            if self.isLeftChild():\n",
    "                \n",
    "                self.parent.leftChild = None\n",
    "            else:\n",
    "                self.parent.rightChild = None\n",
    "        elif self.hasAnyChildren():\n",
    "            if self.hasLeftChild():\n",
    "                \n",
    "                if self.isLeftChild():\n",
    "                    \n",
    "                    self.parent.leftChild = self.leftChild\n",
    "                else:\n",
    "                    \n",
    "                    self.parent.rightChild = self.leftChild\n",
    "                    self.leftChild.parent = self.parent\n",
    "        else:\n",
    "                    \n",
    "            if self.isLeftChild():\n",
    "                        \n",
    "                self.parent.leftChild = self.rightChild\n",
    "            else:\n",
    "                self.parent.rightChild = self.rightChild\n",
    "                self.rightChild.parent = self.parent\n",
    "\n",
    "    def findSuccessor(self):\n",
    "        \n",
    "        succ = None\n",
    "        if self.hasRightChild():\n",
    "            succ = self.rightChild.findMin()\n",
    "        else:\n",
    "            if self.parent:\n",
    "                \n",
    "                if self.isLeftChild():\n",
    "                    \n",
    "                    succ = self.parent\n",
    "                else:\n",
    "                    self.parent.rightChild = None\n",
    "                    succ = self.parent.findSuccessor()\n",
    "                    self.parent.rightChild = self\n",
    "        return succ\n",
    "\n",
    "    def findMin(self):\n",
    "        \n",
    "        current = self\n",
    "        while current.hasLeftChild():\n",
    "            current = current.leftChild\n",
    "        return current\n",
    "\n",
    "    def remove(self,currentNode):\n",
    "        \n",
    "        if currentNode.isLeaf(): #leaf\n",
    "            if currentNode == currentNode.parent.leftChild:\n",
    "                currentNode.parent.leftChild = None\n",
    "            else:\n",
    "                currentNode.parent.rightChild = None\n",
    "        elif currentNode.hasBothChildren(): #interior\n",
    "            \n",
    "            succ = currentNode.findSuccessor()\n",
    "            succ.spliceOut()\n",
    "            currentNode.key = succ.key\n",
    "            currentNode.payload = succ.payload\n",
    "\n",
    "        else: # this node has one child\n",
    "            if currentNode.hasLeftChild():\n",
    "                if currentNode.isLeftChild():\n",
    "                    currentNode.leftChild.parent = currentNode.parent\n",
    "                    currentNode.parent.leftChild = currentNode.leftChild\n",
    "                elif currentNode.isRightChild():\n",
    "                    currentNode.leftChild.parent = currentNode.parent\n",
    "                    currentNode.parent.rightChild = currentNode.leftChild\n",
    "                else:\n",
    "                \n",
    "                    currentNode.replaceNodeData(currentNode.leftChild.key,\n",
    "                                    currentNode.leftChild.payload,\n",
    "                                    currentNode.leftChild.leftChild,\n",
    "                                    currentNode.leftChild.rightChild)\n",
    "            else:\n",
    "                \n",
    "                if currentNode.isLeftChild():\n",
    "                    currentNode.rightChild.parent = currentNode.parent\n",
    "                    currentNode.parent.leftChild = currentNode.rightChild\n",
    "                elif currentNode.isRightChild():\n",
    "                    currentNode.rightChild.parent = currentNode.parent\n",
    "                    currentNode.parent.rightChild = currentNode.rightChild\n",
    "                else:\n",
    "                    currentNode.replaceNodeData(currentNode.rightChild.key,\n",
    "                                    currentNode.rightChild.payload,\n",
    "                                    currentNode.rightChild.leftChild,\n",
    "                                    currentNode.rightChild.rightChild)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "yellow\n",
      "at\n"
     ]
    }
   ],
   "source": [
    "mytree = BinarySearchTree()\n",
    "mytree[3]=\"red\"\n",
    "mytree[4]=\"blue\"\n",
    "mytree[6]=\"yellow\"\n",
    "mytree[2]=\"at\"\n",
    "\n",
    "print(mytree[6])\n",
    "print(mytree[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Check the video for full explanation! **"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}