BST.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search Tree Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Search {10} in bst 10\n",
      "Search {21} in bst False\n",
      "\n",
      "Inorder traverse of BST\n",
      "1\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "10\n",
      "Breadth First Search\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 3, 10, 4, 5, 6]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Node: \n",
    "    def __init__(self,key): \n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = key \n",
    "        \n",
    "class BST:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.length = 0\n",
    "        \n",
    "    def insert(self,value):\n",
    "        new_node = Node(value)\n",
    "        \n",
    "        if self.root is None: \n",
    "            self.root = new_node\n",
    "            self.length +=1\n",
    "        else:\n",
    "            currentNode = self.root\n",
    "            while(True):\n",
    "#                 print(currentNode.val)\n",
    "                if currentNode.val < new_node.val: \n",
    "                    if currentNode.right is None: \n",
    "                        currentNode.right = new_node\n",
    "                        self.length +=1\n",
    "                        return self.length\n",
    "                    else: \n",
    "                        currentNode = currentNode.right\n",
    "                else: \n",
    "                    if currentNode.left is None: \n",
    "                        currentNode.left = new_node \n",
    "                        self.length +=1\n",
    "                        return self.length\n",
    "                    else: \n",
    "                        currentNode = currentNode.left\n",
    "                    \n",
    "    def lookup(self,value):\n",
    "        if self.root == None:\n",
    "            return False\n",
    "        currentNode = self.root;\n",
    "        while(currentNode):\n",
    "            if(value < currentNode.val):\n",
    "                currentNode = currentNode.left\n",
    "            elif(value > currentNode.val):\n",
    "                currentNode = currentNode.right\n",
    "            elif(value == currentNode.val):\n",
    "                return currentNode.val\n",
    "                \n",
    "        return False \n",
    "    \n",
    "    # inoder traversal of the BST \n",
    "    def inorder(self,root): \n",
    "        currentNode = root\n",
    "        if root: \n",
    "            self.inorder(root.left) \n",
    "            print(root.val) \n",
    "            self.inorder(root.right)\n",
    "            \n",
    "    \n",
    "            \n",
    "    def breadthFirstSearch(self):\n",
    "        \"\"\"Breadth First Search\"\"\"\n",
    "        currentNode = self.root\n",
    "        queue = []\n",
    "        bfsList = []\n",
    "        queue.append(currentNode)\n",
    "        \n",
    "        while len(queue) > 0:\n",
    "            currentNode = queue.pop(0)\n",
    "#             print(currentNode.val)\n",
    "            bfsList.append(currentNode.val)\n",
    "            \n",
    "            if currentNode.left:\n",
    "                queue.append(currentNode.left)\n",
    "            if currentNode.right:\n",
    "                queue.append(currentNode.right)\n",
    "                \n",
    "        return bfsList\n",
    "            \n",
    "        \n",
    "        \n",
    "bst = BST()\n",
    "bst.insert(1)\n",
    "bst.insert(3)\n",
    "bst.insert(10)\n",
    "bst.insert(4)\n",
    "bst.insert(5)\n",
    "bst.insert(6)\n",
    "print('Search {10} in bst',bst.lookup(10))\n",
    "print('Search {21} in bst',bst.lookup(21))\n",
    "print('\\nInorder traverse of BST')\n",
    "bst.inorder(bst.root)\n",
    "print(bst.breadthFirstSearch.__doc__)\n",
    "bst.breadthFirstSearch()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tree Traversals (Inorder, Preorder and Postorder) \n",
    "\n",
    "         9\n",
    "      /    \\\n",
    "     4      20\n",
    "    / \\     / \\\n",
    "    1  6   15  170\n",
    "\n",
    "\n",
    "#### Depth First Traversals:\n",
    "1. Inorder (Left, Root, Right) : 1, 4, 6, 9, 15, 20, 170\n",
    "2. Preorder (Root, Left, Right) : 9, 4, 1, 6, 20, 15, 170\n",
    "3. Postorder (Left, Right, Root) : 1, 6, 4, 15, 170, 20, 9\n",
    "\n",
    "#### Breadth First or Level Order Traversal \n",
    "> 9, 4, 20, 1, 6, 15, 170\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Breadth First Search\n",
      "[9, 4, 20, 1, 6, 15, 170]\n",
      "Breadth First Search using Recursion\n",
      "[9, 4, 20, 1, 6, 15, 170]\n",
      "DFS Inorder uisng recursion -> LVR\n",
      "[1, 4, 6, 9, 15, 20, 170]\n",
      "DES Preorder uisng recursion -> VLR\n",
      "[9, 4, 1, 6, 20, 15, 170]\n",
      "DES Postorder uisng recursion -> LRV\n",
      "[1, 6, 4, 15, 170, 20, 9]\n"
     ]
    }
   ],
   "source": [
    "class Node: \n",
    "    def __init__(self,key): \n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = key \n",
    "        \n",
    "class BST:\n",
    "    \"\"\"BST -> Binary Search Tree\"\"\"\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.length = 0\n",
    "        \n",
    "    def insert(self,value):\n",
    "        new_node = Node(value)\n",
    "        \n",
    "        if self.root is None: \n",
    "            self.root = new_node\n",
    "            self.length +=1\n",
    "        else:\n",
    "            currentNode = self.root\n",
    "            while(True):\n",
    "#                 print(currentNode.val)\n",
    "                if currentNode.val < new_node.val:\n",
    "#                     print('right-> ',value)\n",
    "                    if currentNode.right is None: \n",
    "                        currentNode.right = new_node\n",
    "                        self.length +=1\n",
    "                        return self.length\n",
    "                    else: \n",
    "                        currentNode = currentNode.right\n",
    "                else: \n",
    "#                     print('left-> ',value)\n",
    "                    if currentNode.left is None: \n",
    "                        currentNode.left = new_node \n",
    "                        self.length +=1\n",
    "                        return self.length\n",
    "                    else: \n",
    "                        currentNode = currentNode.left\n",
    "    \n",
    "    def breadthFirstSearch(self):\n",
    "        \"\"\"Breadth First Search\"\"\"\n",
    "        currentNode = self.root\n",
    "        queue = []\n",
    "        bfsList = []\n",
    "        queue.append(currentNode)\n",
    "        \n",
    "        while len(queue) > 0:\n",
    "            currentNode = queue.pop(0)\n",
    "#             print(currentNode.val)\n",
    "            bfsList.append(currentNode.val)\n",
    "            \n",
    "            if currentNode.left:\n",
    "                queue.append(currentNode.left)\n",
    "            if currentNode.right:\n",
    "                queue.append(currentNode.right)\n",
    "                \n",
    "        return bfsList\n",
    "    def breadthFirstSearchRecursive(self,queue,bfsList):\n",
    "        \"\"\"Breadth First Search using Recursion\"\"\"\n",
    "        if len(queue) == 0:\n",
    "            return bfsList\n",
    "        currentNode = queue.pop(0)\n",
    "#         print(currentNode.val)\n",
    "        bfsList.append(currentNode.val)\n",
    "        if currentNode.left:\n",
    "            queue.append(currentNode.left)\n",
    "        if currentNode.right:\n",
    "            queue.append(currentNode.right)\n",
    "        \n",
    "        return self.breadthFirstSearchRecursive(queue,bfsList)\n",
    "    \n",
    "    def DFSOLDWAYInorder(self,root): \n",
    "        \"\"\"DFS -> 1. inoder traversal of the BST \"\"\"\n",
    "        currentNode = root\n",
    "        if root: \n",
    "            self.DFSInorder(root.left) \n",
    "            print(root.val) \n",
    "            self.DFSInorder(root.right)\n",
    "    def DFSInorder(self):\n",
    "        \"\"\"DFS Inorder uisng recursion -> LVR\"\"\"\n",
    "        return traverseInOrder(self.root,[])\n",
    "    def DFSPreorder(self):\n",
    "        \"\"\"DES Preorder uisng recursion -> VLR\"\"\"\n",
    "        return traversePreOrder(self.root,[])\n",
    "    def DFSPostorder(self):\n",
    "        \"\"\"DES Postorder uisng recursion -> LRV\"\"\"\n",
    "        return traversePostOrder(self.root,[])\n",
    "\n",
    "            \n",
    "def traverseInOrder(node,InLst):\n",
    "    \"\"\"LVR -> Left Root RIght\"\"\"\n",
    "#     print(node.val)\n",
    "#     print(InLst)\n",
    "    if node.left:\n",
    "        traverseInOrder(node.left,InLst)\n",
    "    InLst.append(node.val)\n",
    "    if node.right:\n",
    "        traverseInOrder(node.right,InLst)\n",
    "    return InLst   \n",
    "\n",
    "def traversePreOrder(node,PreLst):\n",
    "    \"\"\"VLR -> Root Left Right\"\"\"\n",
    "#     print(node.val)\n",
    "#     print(PreLst)\n",
    "    PreLst.append(node.val)\n",
    "    if node.left:\n",
    "        traversePreOrder(node.left,PreLst)\n",
    "    if node.right:\n",
    "        traversePreOrder(node.right,PreLst)\n",
    "    return PreLst\n",
    "\n",
    "def traversePostOrder(node,PostLst):\n",
    "    \"\"\"LRV -> Left Right Root\"\"\"\n",
    "#     print(node.val)\n",
    "#     print(PostLst)\n",
    "    if node.left:\n",
    "        traversePostOrder(node.left,PostLst)\n",
    "    if node.right:\n",
    "        traversePostOrder(node.right,PostLst)\n",
    "    PostLst.append(node.val)\n",
    "    \n",
    "    return PostLst\n",
    "        \n",
    "        \n",
    "bst = BST()\n",
    "bst.insert(9)\n",
    "bst.insert(4)\n",
    "bst.insert(6)\n",
    "bst.insert(20)\n",
    "bst.insert(170)\n",
    "bst.insert(15)\n",
    "bst.insert(1)\n",
    "print(bst.breadthFirstSearch.__doc__)\n",
    "print(bst.breadthFirstSearch())\n",
    "print(bst.breadthFirstSearchRecursive.__doc__)\n",
    "print(bst.breadthFirstSearchRecursive([bst.root],[]))\n",
    "print(bst.DFSInorder.__doc__)\n",
    "print(bst.DFSInorder())\n",
    "print(bst.DFSPreorder.__doc__)\n",
    "print(bst.DFSPreorder())\n",
    "print(bst.DFSPostorder.__doc__)\n",
    "print(bst.DFSPostorder())"
   ]
  },
  {
   "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}