Binary_Tree_Assignment_Day4.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import unittest\n",
    "import numpy as np\n",
    "\n",
    "# https://github.com/joowani/binarytree\n",
    "# This is used only for Displaying the tree.\n",
    "# https://binarytree.readthedocs.io/en/latest/specs.html\n",
    "from binarytree import build \n",
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, d):\n",
    "        self.data = d\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def insert(self, d):\n",
    "        # This is when we don't allow duplicates, here we are allowing\n",
    "        # if we do not want to allow the duplicates\n",
    "        # just uncomment first two line and instead of < lt use <= lteq afterwards.\n",
    "        \n",
    "        #if self.data == d:\n",
    "        #    return False\n",
    "        # This is done to make pretty print work, \n",
    "        if d == None:\n",
    "            return\n",
    "        \n",
    "        if d <= self.data:\n",
    "            if self.left:\n",
    "                self.left.insert(d)\n",
    "            else:\n",
    "                self.left = Node(d)\n",
    "                return True\n",
    "        else:\n",
    "            if self.right:\n",
    "                self.right.insert(d)\n",
    "            else:\n",
    "                self.right = Node(d)\n",
    "                return True\n",
    "\n",
    "    \n",
    "    def preorder(self, l):\n",
    "        l.append(self.data)\n",
    "        if self.left:\n",
    "            self.left.preorder(l)\n",
    "        if self.right:\n",
    "            self.right.preorder(l)\n",
    "        return l\n",
    "            \n",
    "    def postorder(self, l):\n",
    "        if self.left:\n",
    "            self.left.postorder(l)\n",
    "        if self.right:\n",
    "            self.right.postorder(l)\n",
    "        l.append(self.data)\n",
    "        return l\n",
    "    \n",
    "    def inorder(self, l):\n",
    "        if self.left:\n",
    "            self.left.inorder(l)\n",
    "        l.append(self.data)\n",
    "        if self.right:\n",
    "            self.right.inorder(l)\n",
    "        return l\n",
    "    \n",
    "    def levelorder(self, l, queue = deque()):\n",
    "        l.append(self.data)\n",
    "        [queue.append(node) for node in [self.left, self.right] if node]\n",
    "        if queue:\n",
    "            queue.popleft().levelorder(l, queue)\n",
    "        return l\n",
    "            \n",
    "    def levelorder2(self, l, head, queue = deque()):\n",
    "        if head is None:\n",
    "            return l\n",
    "        l.append(head.data)\n",
    "        [queue.append(node) for node in [head.left, head.right] if node]\n",
    "        if queue:\n",
    "            self.levelorder2(l, queue.popleft(), queue)\n",
    "        return l\n",
    "        \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TestNode(unittest.TestCase):\n",
    "    #def setUp(self):\n",
    "    #    self.node = Node(d)\n",
    "    def test_insert(self):\n",
    "        \n",
    "        #random_numbers = np.random.randint(low = 50, high = 100, size = 9)\n",
    "        #random_numbers = [61, 94, 98, 51, 95, 94, 58, 50, 81]\n",
    "        random_numbers = [61, 51, 94, 50, 58, 94, 98, None, None, None, None, 81, None, 95, None]\n",
    "        node = Node(random_numbers[0])\n",
    "        \n",
    "        #print(random_numbers)\n",
    "        print(build(random_numbers))\n",
    "        \n",
    "        for i in [j for j in range(len(random_numbers)) if j != 0]:\n",
    "            node.insert(random_numbers[i])\n",
    "            \n",
    "        #print(node.levelorder2([], node, deque()))\n",
    "            \n",
    "        inorder_list = [50, 51, 58, 61, 81, 94, 94, 95, 98]\n",
    "        \n",
    "        preorder_list = [61, 51, 50, 58, 94, 94, 81, 98, 95]\n",
    "        \n",
    "        postorder_list = [50, 58, 51, 81, 94, 95, 98, 94, 61]\n",
    "        \n",
    "        levelorder_list = [61, 51, 94, 50, 58, 94, 98, 81, 95]\n",
    "        \n",
    "        #print(inorder_list)\n",
    "            \n",
    "        self.assertEqual(inorder_list, node.inorder([]))\n",
    "        \n",
    "        self.assertEqual(preorder_list, node.preorder([]))\n",
    "        \n",
    "        self.assertEqual(postorder_list, node.postorder([]))\n",
    "        \n",
    "        self.assertEqual(levelorder_list, node.levelorder([]))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "."
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "     ____61______\n",
      "    /            \\\n",
      "  _51            _94___\n",
      " /   \\          /      \\\n",
      "50    58      _94      _98\n",
      "             /        /\n",
      "            81       95\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.001s\n",
      "\n",
      "OK\n"
     ]
    }
   ],
   "source": [
    "if __name__ == '__main__':\n",
    "    unittest.main(TestNode(), argv=['first-arg-is-ignored'], exit=False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BST(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    \n",
    "    # For now it will return true for all the values since we are allowind duplicates\n",
    "    def insert(self, d):\n",
    "        \n",
    "        # This is done to make pretty print work, \n",
    "        if d == None:\n",
    "            return\n",
    "        \n",
    "        if self.root:\n",
    "            return self.root.insert(d)\n",
    "        else:\n",
    "            self.root = Node(d)\n",
    "            return True\n",
    "    \n",
    "    def preorder(self):\n",
    "        if self.root:\n",
    "            return self.root.preorder([])\n",
    "        else:\n",
    "            return []\n",
    "        \n",
    "    \n",
    "    def postorder(self):\n",
    "        if self.root:\n",
    "            return self.root.postorder([])\n",
    "        else:\n",
    "            return []\n",
    "    \n",
    "    \n",
    "    def inorder(self):\n",
    "        if self.root:\n",
    "            return self.root.inorder([])\n",
    "        else:\n",
    "            return []\n",
    "        \n",
    "    def levelorder(self):\n",
    "        if self.root:\n",
    "            return self.root.levelorder([])\n",
    "        else:\n",
    "            return []\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TestBST(unittest.TestCase):\n",
    "    \n",
    "    def setUp(self):\n",
    "        self.bst = BST()\n",
    "        \n",
    "    def test_insert(self):\n",
    "        \n",
    "        #random_numbers = np.random.randint(low = 50, high = 100, size = 9)\n",
    "        #random_numbers = [61, 94, 98, 51, 95, 94, 58, 50, 81]\n",
    "        random_numbers = [61, 51, 94, 50, 58, 94, 98, None, None, None, None, 81, None, 95, None]\n",
    "        \n",
    "        #print(random_numbers)\n",
    "        print(build(random_numbers))\n",
    "        \n",
    "        for num in random_numbers:\n",
    "            self.bst.insert(num)\n",
    "        \n",
    "        inorder_list = [50, 51, 58, 61, 81, 94, 94, 95, 98]\n",
    "        \n",
    "        preorder_list = [61, 51, 50, 58, 94, 94, 81, 98, 95]\n",
    "        \n",
    "        postorder_list = [50, 58, 51, 81, 94, 95, 98, 94, 61]\n",
    "        \n",
    "        levelorder_list = [61, 51, 94, 50, 58, 94, 98, 81, 95]\n",
    "        \n",
    "        #print(inorder_list)\n",
    "            \n",
    "        self.assertEqual(inorder_list, self.bst.inorder())\n",
    "        \n",
    "        self.assertEqual(preorder_list, self.bst.preorder())\n",
    "        \n",
    "        self.assertEqual(postorder_list, self.bst.postorder())\n",
    "        \n",
    "        self.assertEqual(levelorder_list, self.bst.levelorder())\n",
    "        \n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "."
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "     ____61______\n",
      "    /            \\\n",
      "  _51            _94___\n",
      " /   \\          /      \\\n",
      "50    58      _94      _98\n",
      "             /        /\n",
      "            81       95\n",
      "\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.002s\n",
      "\n",
      "OK\n"
     ]
    }
   ],
   "source": [
    "if __name__ == '__main__':\n",
    "    unittest.main(TestBST(), argv=['first-arg-is-ignored'], exit=False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[61, 51, 94, 50, 58, 94, 98, None, None, None, None, 81, None, 95]\n",
      "\n",
      "     ____61______\n",
      "    /            \\\n",
      "  _51            _94___\n",
      " /   \\          /      \\\n",
      "50    58      _94      _98\n",
      "             /        /\n",
      "            81       95\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from binarytree import build\n",
    "\n",
    "\n",
    "values = [61, 51, 94, 50, 58, 94, 98, None, None, None, None, 81, None, 95, None]\n",
    "root = build(values)\n",
    "print(root.values)\n",
    "\n",
    "print(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}