11-09-15-exercises (trees).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "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",
    "    # overwrite the len()\n",
    "    def __len__(self):\n",
    "        return self.size\n",
    "    \n",
    "    def __iter__(self):\n",
    "        return self.root.__iter__()\n",
    "    \n",
    "    def insertNode(self, val):\n",
    "        if self.root:\n",
    "            self.__insertNode(val, self.root)\n",
    "        else:\n",
    "            self.root = TreeNode(val)\n",
    "        self.size += 1\n",
    "    \n",
    "    # private function. value of child of left is smaller than root.\n",
    "    def __insertNode(self, val, tNode):\n",
    "        \n",
    "        if val < tNode.data:\n",
    "            if tNode.lChild is None:\n",
    "                tNode.lChild = TreeNode(val)\n",
    "            else:\n",
    "                self.__insertNode(val, tNode.lChild)\n",
    "        else:\n",
    "            if tNode.rChild is None:\n",
    "                tNode.rChild = TreeNode(val)\n",
    "            else:\n",
    "                self.__insertNode(val, tNode.rChild)\n",
    "    \n",
    "    # perform a pre-order traversal of the tree\n",
    "    def preOrder(self):\n",
    "        if self.root is not None:\n",
    "            self.__preOrder(self.root)\n",
    "        else:\n",
    "            print(None)\n",
    "    \n",
    "    def __preOrder(self, tNode):\n",
    "        if tNode is None:\n",
    "            return\n",
    "        else:\n",
    "            print(str(tNode.data))\n",
    "            self.__preOrder(tNode.lChild)\n",
    "            self.__preOrder(tNode.rChild)\n",
    "    \n",
    "    def inOrder(self):\n",
    "        if self.root is not None:\n",
    "            self.__inOrder(self.root)\n",
    "        else:\n",
    "            print(None)\n",
    "    \n",
    "    def __inOrder(self, tNode):\n",
    "        if tNode is None:\n",
    "            return\n",
    "        else:\n",
    "            self.__preOrder(tNode.lChild)\n",
    "            print(str(tNode.data))\n",
    "            self.__preOrder(tNode.rChild)     \n",
    "\n",
    "    def postOrder(self):\n",
    "        if self.root is not None:\n",
    "            self.__postOrder(self.root)\n",
    "        else:\n",
    "            print(None)\n",
    "    \n",
    "    def __postOrder(self, tNode):\n",
    "        if tNode is None:\n",
    "            return\n",
    "        else:\n",
    "            self.__postOrder(tNode.lChild)\n",
    "            self.__postOrder(tNode.rChild)\n",
    "            print(str(tNode.data))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class TreeNode():\n",
    "    def __init__(self, val):\n",
    "        self.lChild = None\n",
    "        self.rChild = None\n",
    "        self.data = val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "aBST = BinarySearchTree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "aBST.insertNode(ord('F'))\n",
    "aBST.insertNode(ord('D'))\n",
    "aBST.insertNode(ord('B'))\n",
    "aBST.insertNode(ord('E'))\n",
    "aBST.insertNode(ord('A'))\n",
    "aBST.insertNode(ord('C'))\n",
    "\n",
    "aBST.insertNode(ord('J'))\n",
    "aBST.insertNode(ord('G'))\n",
    "aBST.insertNode(ord('I'))\n",
    "aBST.insertNode(ord('K'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "70\n",
      "68\n",
      "66\n",
      "65\n",
      "67\n",
      "69\n",
      "74\n",
      "71\n",
      "73\n",
      "75\n"
     ]
    }
   ],
   "source": [
    "aBST.preOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def calcHeight(node):\n",
    "    if node is None:\n",
    "        return 0\n",
    "    else:\n",
    "        myHeight = max(calcHeight(node.lChild), calcHeight(node.rChild)) + 1\n",
    "        return myHeight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "print(calcHeight(aBST.root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def isBalanced(node):\n",
    "    \n",
    "    if node is None:\n",
    "        return True\n",
    "    else:\n",
    "        leftHeight = calcHeight(node.lChild)\n",
    "        rightHeight = calcHeight(node.rChild)\n",
    "        \n",
    "        print(\"leftHeight=\" + str(leftHeight))\n",
    "        print(\"rightHeight=\" + str(rightHeight))\n",
    "        diff = abs(leftHeight - rightHeight)\n",
    "        \n",
    "        if diff > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return isBalanced(node.lChild) and isBalanced(node.rChild)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "leftHeight=3\n",
      "rightHeight=4\n",
      "leftHeight=2\n",
      "rightHeight=1\n",
      "leftHeight=1\n",
      "rightHeight=1\n",
      "leftHeight=0\n",
      "rightHeight=0\n",
      "leftHeight=0\n",
      "rightHeight=0\n",
      "leftHeight=0\n",
      "rightHeight=0\n",
      "leftHeight=2\n",
      "rightHeight=3\n",
      "leftHeight=0\n",
      "rightHeight=1\n",
      "leftHeight=0\n",
      "rightHeight=0\n",
      "leftHeight=0\n",
      "rightHeight=2\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(isBalanced(aBST.root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "aBST.insertNode(ord('Q'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "70\n",
      "68\n",
      "66\n",
      "65\n",
      "67\n",
      "69\n",
      "74\n",
      "71\n",
      "73\n",
      "75\n",
      "80\n",
      "81\n"
     ]
    }
   ],
   "source": [
    "aBST.preOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "# Bad way to insert values into tree to create a BST. Max height.\n",
    "\n",
    "A = [1, 2, 3, 4, 5, 6, 7]\n",
    "\n",
    "testBST = BinarySearchTree()\n",
    "\n",
    "for i in A:\n",
    "    testBST.insertNode(i)\n",
    "\n",
    "print(calcHeight(testBST.root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insertSmart(A):\n",
    "    \n",
    "    lenA = len(A)\n",
    "    \n",
    "    if not A:\n",
    "        return\n",
    "    \n",
    "    if lenA == 1:\n",
    "        testBST.insertNode(A[0])\n",
    "    elif lenA == 2:\n",
    "        testBST.insertNode(A[1])\n",
    "        testBST.insertNode(A[0])\n",
    "    else:\n",
    "        pos = lenA // 2\n",
    "        leftSide = A[:pos]\n",
    "        rightSide = A[pos+1:]\n",
    "        testBST.insertNode(A[pos])\n",
    "        insertSmart(leftSide)\n",
    "        insertSmart(rightSide)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "A = [1, 2, 3, 4, 5, 6, 7]\n",
    "testBST = BinarySearchTree()\n",
    "insertSmart(A)\n",
    "print(calcHeight(testBST.root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}