Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What are trees\n",
    "Trees are data structures with 3 parts: a Root, Branches, and Leaves, just like a normal tree. The difference is that in programming, the root of a tree is at the top, and the leaves are at the bottom. One main example of a tree is a classification tree for animals. One main property you will see is that all animals at the bottom are still animals, as defined by the root. Another property of trees is that all children of one node are independant from the children of another node. a third property is that each leaf is unique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tree Vocab\n",
    "\n",
    "\n",
    "1. Node: a node is a fundamental part of a tree. it can have a name, which is known as a key. A node can also carry additional info, called the payload. the payload is not central, but many programs do use it and take advantage\n",
    "\n",
    "\n",
    "2. Edge: a line that connects two nodes to show a connection. Every node but the root is connected with exactly one incoming edge from another node( one input per node and multiple outgoing edges ), like the opposite of a function table( one output per node but can have multiple incoming edges ).\n",
    "\n",
    "\n",
    "3. Root: the only part that has no incoming edge, as it is the origin.\n",
    "\n",
    "\n",
    "4. Path: an ordered list of nodes that are all connected with a single edge between each ( like a food chain )\n",
    "\n",
    "\n",
    "5. Children: the set of nodes that have incoming edges from the same node that are the children of the same node.\n",
    "\n",
    "\n",
    "6. Parent: the node that is the parent of all the nodes it connects to with outgoing edges. \n",
    "\n",
    "\n",
    "7. Leaf node: Leaf nodes are nodes without children.\n",
    "\n",
    "\n",
    "8. Level: The level of a node is the number of edges from the root node to the node specified.\n",
    "\n",
    "\n",
    "9. Height: The height of a tree is the largest level of all the nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tree Implementation (list)\n",
    "\n",
    "\n",
    "WE are going to implement a tree as a 2d list ( a list of lists ). In a list of lists tree, we will store the value of the root node as the first element of the list.\n",
    "The second element of the list will itself be a list that represents the left subtree. \n",
    "The third element of the list will be another list that represents the right subtree. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#creates a binary tree\n",
    "def BinaryTree(r):\n",
    "    return [r, [], []]\n",
    "\n",
    "#Adds a new node to the left of the tree\n",
    "def insertLeft(root,newBranch):\n",
    "    #Gets value of current left child\n",
    "    t = root.pop(1)\n",
    "    #Checks if current left child is empty or not\n",
    "    if len(t) > 1:\n",
    "        # If it isn't empty, creates a new subtree with new root provided\n",
    "        root.insert(1,[newBranch,t,[]])\n",
    "    else:\n",
    "        #otherwise, just make it the child\n",
    "        root.insert(1,[newBranch, [], []])\n",
    "    return root\n",
    "#Same as the above with minor changes\n",
    "def insertRight(root,newBranch):\n",
    "    t = root.pop(2)\n",
    "    if len(t) > 1:\n",
    "        root.insert(2,[newBranch,[],t])\n",
    "    else:\n",
    "        root.insert(2,[newBranch,[],[]])\n",
    "    return root\n",
    "#Returns value of node\n",
    "def getRootVal(root):\n",
    "    return root[0]\n",
    "#Sets value of node\n",
    "def setRootVal(root,newVal):\n",
    "    root[0] = newVal\n",
    "#Returns left child\n",
    "def getLeftChild(root):\n",
    "    return root[1]\n",
    "#Returns right child\n",
    "def getRightChild(root):\n",
    "    return root[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "factor32 = BinaryTree(32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[32, [2, [], []], []]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insertLeft(factor32,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[32, [2, [], []], [16, [], []]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insertRight(factor32,16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Node implementation \n",
    "We are going to implement a class node with 3 attributes: a  left and right subtree and a value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree(object):\n",
    "    def __init__(self,root):\n",
    "        self.key = root\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    \n",
    "    def insert_left(self,obj):\n",
    "        if self.left == None:\n",
    "            ntree = BinaryTree(obj)\n",
    "            self.left = ntree\n",
    "        else:\n",
    "            ntree = BinaryTree(obj)\n",
    "            ntree.left = self.left\n",
    "            self.left = ntree\n",
    "        \n",
    "    def insert_right(self,obj):\n",
    "        if self.right == None:\n",
    "            ntree = BinaryTree(obj)\n",
    "            self.right = ntree\n",
    "        else:\n",
    "            ntree = BinaryTree(obj)\n",
    "            ntree.right = self.right\n",
    "            self.right = ntree\n",
    "            \n",
    "    def getLeft(self):\n",
    "        return self.left\n",
    "    \n",
    "    def getRight(self):\n",
    "        return self.right\n",
    "    \n",
    "    def setVal(self,val):\n",
    "        self.key =val\n",
    "        \n",
    "    def getVal(self):\n",
    "        return self.key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Creates factor tree of 32\n",
    "f32 = BinaryTree(32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "#sets left end of factor tree to 16 and right end to 2\n",
    "f32.insert_left(16)\n",
    "f32.insert_right(2)\n",
    "#Sets left end of factor tree of 16 to 8 and right end to 2\n",
    "f32.left.insert_left(8)\n",
    "f32.left.insert_right(2)\n",
    "#Factors 8\n",
    "f32.left.left.insert_left(4)\n",
    "f32.left.left.insert_right(2)\n",
    "#Factors 4\n",
    "f32.left.left.left.insert_left(2)\n",
    "f32.left.left.left.insert_right(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an image representation of the tree we just built:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.getVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.left.getVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.right.getVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.left.left.getVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.left.right.getVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.left.left.left.getVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.left.left.right.getVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.left.left.left.left.getVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f32.left.left.left.right.getVal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tree Traversals\n",
    "\n",
    "There are 3 main methods to traverse (travel through) a tree. Each one of these three methods can travel to all nodes in a tree, the difference is the order they visit in. \n",
    "\n",
    "\n",
    "1. Preorder: For a preorder traversal, we visit the root node first, then we recursivley do a preorder traversal through the left subtree then the right subtree.\n",
    "\n",
    "\n",
    "2. Postorder: In a postorder traversal, we recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node.\n",
    "\n",
    "\n",
    "3. Inorder: We recursivley do an inorder traversal of the left subtree, visit the root, then recursively do an inorder traversal of the right subtree.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Sets up tree\n",
    "class BinaryTree(object):\n",
    "    def __init__(self,root):\n",
    "        self.key = root\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    \n",
    "    def insert_left(self,obj):\n",
    "        if self.left == None:\n",
    "            ntree = BinaryTree(obj)\n",
    "            self.left = ntree\n",
    "        else:\n",
    "            ntree = BinaryTree(obj)\n",
    "            ntree.left = self.left\n",
    "            self.left = ntree\n",
    "        \n",
    "    def insert_right(self,obj):\n",
    "        if self.right == None:\n",
    "            ntree = BinaryTree(obj)\n",
    "            self.right = ntree\n",
    "        else:\n",
    "            ntree = BinaryTree(obj)\n",
    "            ntree.right = self.right\n",
    "            self.right = ntree\n",
    "            \n",
    "    def getLeft(self):\n",
    "        return self.left\n",
    "    \n",
    "    def getRight(self):\n",
    "        return self.right\n",
    "    \n",
    "    def setVal(self,val):\n",
    "        self.key =val\n",
    "        \n",
    "    def getVal(self):\n",
    "        return self.key\n",
    "    \n",
    "#Creates Tree\n",
    "f32 = BinaryTree(32)\n",
    "#sets left end of factor tree to 16 and right end to 2\n",
    "f32.insert_left(16)\n",
    "f32.insert_right(2)\n",
    "#Sets left end of factor tree of 16 to 8 and right end to 2\n",
    "f32.left.insert_left(8)\n",
    "f32.left.insert_right(2)\n",
    "#Factors 8\n",
    "f32.left.left.insert_left(4)\n",
    "f32.left.left.insert_right(2)\n",
    "#Factors 4\n",
    "f32.left.left.left.insert_left(2)\n",
    "f32.left.left.left.insert_right(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Preorder(tree):\n",
    "    if tree:\n",
    "        print(tree.key)\n",
    "        Preorder(tree.left)\n",
    "        Preorder(tree.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "32\n",
      "16\n",
      "8\n",
      "4\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "Preorder(f32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Postorder(tree):\n",
    "    if tree:\n",
    "        Postorder(tree.left)\n",
    "        Postorder(tree.right)\n",
    "        print(tree.key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "2\n",
      "4\n",
      "2\n",
      "8\n",
      "2\n",
      "16\n",
      "2\n",
      "32\n"
     ]
    }
   ],
   "source": [
    "Postorder(f32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Inorder(tree):\n",
    "    if tree:\n",
    "        Inorder(tree.left)\n",
    "        print(tree.key)\n",
    "        Inorder(tree.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "e\n",
      "2\n",
      "4\n",
      "2\n",
      "8\n",
      "2\n",
      "16\n",
      "2\n",
      "32\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "Inorder(f32)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an image to represent the path of traversal for each type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1,[2,3,4],5]\n",
    "sol = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ans(tree):\n",
    "    global sol\n",
    "    if type(tree)!=list:\n",
    "        sol.insert(0,tree)\n",
    "    else:\n",
    "        ans(tree[1])\n",
    "        ans(tree[2])\n",
    "        sol.insert(0,tree[0])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "ans(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 5, 2, 4, 3]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sol"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary heap & priority queue\n",
    "\n",
    "One important variation of a queue is called a priority queue. \n",
    "A priority queue acts like a queue in that you dequeue an item by removing it from the front. \n",
    "However, in a priority queue the logical order of items inside a queue is determined by their priority\n",
    "The highest priority items are at the front of the queue and the lowest priority items are at the back. \n",
    "When you enqueue an item on a priority queue, the new item may move all the way to the front\n",
    "The classic way to implement a priority queue is using a data structure called a binary heap. \n",
    "A binary heap will allow us both enqueue and dequeue items in O(logn)!\n",
    "The binary heap has two common variations: the min heap, in which the smallest key is always at the front, and the max heap, in which the largest key value is always at the front. \n",
    "In this section we will implement the min heap.\n",
    "The heap will have the following methods:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BinaryHeap() creates a new, empty, binary heap.\n",
    "\n",
    "insert(k) adds a new item to the heap.\n",
    "\n",
    "findMin() returns the item with the minimum key value, leaving item in the heap.\n",
    "\n",
    "delMin() returns the item with the minimum key value, removing the item from the heap.\n",
    "\n",
    "isEmpty() returns true if the heap is empty, false otherwise.\n",
    "\n",
    "size() returns the number of items in the heap.\n",
    "\n",
    "buildHeap(list) builds a new heap from a list of keys.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "We will be implementing the heap as a list, where the first element is 0, and the next element is the root. to find the left child of any node, just go to the index that is double the parent. for the right child, do the same but add one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinHeap:\n",
    "    def __init__(self):\n",
    "        self.heapList = [0]\n",
    "        self.currentSize = 0\n",
    "\n",
    "\n",
    "    def percUp(self,i):\n",
    "        \n",
    "        while i // 2 > 0:\n",
    "            \n",
    "            if self.heapList[i] < self.heapList[i // 2]:\n",
    "                \n",
    "            \n",
    "                tmp = self.heapList[i // 2]\n",
    "                self.heapList[i // 2] = self.heapList[i]\n",
    "                self.heapList[i] = tmp\n",
    "            i = i // 2\n",
    "\n",
    "    def insert(self,k):\n",
    "        \n",
    "        self.heapList.append(k)\n",
    "        self.currentSize = self.currentSize + 1\n",
    "        self.percUp(self.currentSize)\n",
    "\n",
    "    def percDown(self,i):\n",
    "        \n",
    "        while (i * 2) <= self.currentSize:\n",
    "            \n",
    "            mc = self.minChild(i)\n",
    "            if self.heapList[i] > self.heapList[mc]:\n",
    "                \n",
    "                tmp = self.heapList[i]\n",
    "                self.heapList[i] = self.heapList[mc]\n",
    "                self.heapList[mc] = tmp\n",
    "            i = mc\n",
    "\n",
    "    def minChild(self,i):\n",
    "        \n",
    "        if i * 2 + 1 > self.currentSize:\n",
    "            \n",
    "            return i * 2\n",
    "        else:\n",
    "            \n",
    "            if self.heapList[i*2] < self.heapList[i*2+1]:\n",
    "                return i * 2\n",
    "            else:\n",
    "                return i * 2 + 1\n",
    "\n",
    "    def delMin(self):\n",
    "        retval = self.heapList[1]\n",
    "        self.heapList[1] = self.heapList[self.currentSize]\n",
    "        self.currentSize = self.currentSize - 1\n",
    "        self.heapList.pop()\n",
    "        self.percDown(1)\n",
    "        return retval\n",
    "\n",
    "    def buildHeap(self,alist):\n",
    "        i = len(alist) // 2\n",
    "        self.currentSize = len(alist)\n",
    "        self.heapList = [0] + alist[:]\n",
    "        while (i > 0):\n",
    "            self.percDown(i)\n",
    "            i = i - 1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Binary Search Trees are trees that follow one main property: Keys greater than the parent are in the right subtree, and Keys lesser than the parent are in the left subtree. This is the BST property. Here is how we create a binary search tree by inserting nodes in this order: 70,31,93, 94,14,23,73: we will first make 70 the root node, as it is the first number. THen, we will put 31 to the left and 93 to the right of 70. Then, we find that, because 94 is greater than 70 and 93, it will go to the right of 93. Then, we see that 14 is less than 31 and 70, so it goes to the left of 31. Then, we see that 23 is less than 70, less than 31, but greater than 14, so it will go to teh right of 14. Finally, we see that 73 is greater than 70 but less than 93, so it goes to the left of 93. To code out the search tree, we will use a node system similar to the linked list implementation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will be making 2 classes, called BinarySearchTree and TreeNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "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",
    "    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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interview Q 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Sets up tree\n",
    "class BinaryTree(object):\n",
    "    def __init__(self,root):\n",
    "        self.key = root\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "    \n",
    "    def insert_left(self,obj):\n",
    "        if self.left == None:\n",
    "            ntree = BinaryTree(obj)\n",
    "            self.left = ntree\n",
    "        else:\n",
    "            ntree = BinaryTree(obj)\n",
    "            ntree.left = self.left\n",
    "            self.left = ntree\n",
    "        \n",
    "    def insert_right(self,obj):\n",
    "        if self.right == None:\n",
    "            ntree = BinaryTree(obj)\n",
    "            self.right = ntree\n",
    "        else:\n",
    "            ntree = BinaryTree(obj)\n",
    "            ntree.right = self.right\n",
    "            self.right = ntree\n",
    "            \n",
    "    def getLeft(self):\n",
    "        return self.left\n",
    "    \n",
    "    def getRight(self):\n",
    "        return self.right\n",
    "    \n",
    "    def setVal(self,val):\n",
    "        self.key =val\n",
    "        \n",
    "    def getVal(self):\n",
    "        return self.key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Creates Tree\n",
    "t = BinaryTree(20)\n",
    "t.insert_left(19)\n",
    "t.insert_right(21)\n",
    "t.left.insert_left(18)\n",
    "t.left.insert_right(20)\n",
    "t.right.insert_right(50)\n",
    "t.right.right.insert_left(40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "parents = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Postorder(tree):\n",
    "    global parents\n",
    "    if tree:\n",
    "        Postorder(tree.left)\n",
    "        Postorder(tree.right)\n",
    "        if tree.left != None or tree.right != None:\n",
    "            parents.append(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Solve(tree,parents):\n",
    "    Postorder(tree)\n",
    "    for parent in parents:\n",
    "        if parent.left != None:\n",
    "            if parent.left.key > parent.key:\n",
    "                return False\n",
    "            print('L ',parent.key,parent.left.key)\n",
    "        if parent.right != None:\n",
    "            if parent.right.key < parent.key:\n",
    "                return False\n",
    "            print('R ',parent.key,parent.right.key)\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L  19 18\n",
      "R  19 20\n",
      "L  50 40\n",
      "R  21 50\n",
      "L  20 19\n",
      "R  20 21\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(Solve(t,parents))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color = 'red'>IMPORTANT NOTE:</font>\n",
    "This above solution is actually incorrect. It is important to note that BST Property not only says that the right child of a node must be greater and the left lesser, it says that the __ENTIRE LEFT SUBTREE__ must be lesser and the __ENTIRE RIGHT SUBTREE__ must be greater. To solve, what we will do is first initialize the Node class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val = None):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we know that we need to keep track of the minimum and maximum values a node can take for it to satisfy the BST property. For each node, we will check if its value is within the minimum and maximum value. Note that a node can be from infinity to negative infinity. Let's set our infinity variables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "infinity = float('infinity')\n",
    "negative_infinity = float('-infinity')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we keep in mind the BST property - for any node, its left child must be less than or equal to its value and the right child must be greater than or equal to its value. To solve, what we will do is recursively go through our tree and send the current value as the new max to our left child and have the minimum stay the same, and with the right child we set the current value as the new min, and have the max not change. Let's create our function here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Our recursive function takes in the root node as Tree and takes the max and min values as inputs\n",
    "#which default to infinity and negative infinity\n",
    "def isBST(tree, minVal = negative_infinity, maxVal = infinity):\n",
    "    \n",
    "    #Now, we check if the tree is empty (edge case)\n",
    "    if tree is None:\n",
    "        return True\n",
    "    \n",
    "    #Now, we check if the tree value fits within the constraints of the minimum and maximum values\n",
    "    if not minVal <= tree.val <= maxVal:\n",
    "        return False\n",
    "    \n",
    "    #Now, we do a recursive call for the left and right children. As described above, the min and\n",
    "    #max values change accordingly.\n",
    "    return isBST(tree.left,minVal,tree.val) and isBst(tree.right,tree.val,maxVal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### _ALTERNATE SOLUTION_\n",
    "\n",
    "If there is no constraint on space complexity, we can use a sneaky rule to solve this, which says that, in a binary search tree, if you do an inorder traversal, you will get the nodes in a sorted order. Let's implement that:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBST2(tree,lastNode = [negative_infinity]):\n",
    "    \n",
    "    #Edge case if the tree is empty\n",
    "    if tree is None:\n",
    "        return True\n",
    "    \n",
    "    #Checks if the isBST2 function on the left node is returning false: if it is,\n",
    "    #that means that it is a BST tree so far. It would return false if the other one\n",
    "    #returned false, creating a chain reaction ending the whole recursion. It would\n",
    "    #actually start returning false because of the next if statement\n",
    "    if not isBST2(tree.left,lastNode):\n",
    "        return False\n",
    "    \n",
    "    #This if statement checks if the tree value is less than the previous item in the\n",
    "    #inorder search - if it goes through, that means that the tree is not a BST\n",
    "    if tree.val < lastNode[0]:\n",
    "        return False\n",
    "    \n",
    "    #This sets the lastNode to the tree value, for further comparisons\n",
    "    lastNode[0] = tree.val\n",
    "    \n",
    "    #This part continues the Inorder search\n",
    "    return isBST2(tree.right,lastNode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Interview Q 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val = None):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def TreeLevelPrint(tree):\n",
    "    if not tree:\n",
    "        return\n",
    "    deque = [tree]\n",
    "    topop = []\n",
    "    showd = [tree.val]\n",
    "    showt = []\n",
    "    i = 0\n",
    "    while deque:\n",
    "        for i in deque:\n",
    "            if i.left:\n",
    "                topop.append(i.left)\n",
    "                showt.append(i.left.val)\n",
    "            if i.right:\n",
    "                topop.append(i.right)\n",
    "                showt.append(i.right.val)\n",
    "        print(showd)\n",
    "        deque = topop[:]\n",
    "        showd = showt[:]        \n",
    "        topop = []\n",
    "        showt = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "[2, 3]\n",
      "[4, 5, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "root = Node(1)\n",
    "root.left = Node(2)\n",
    "root.right = Node(3)\n",
    "root.right.left = Node(6)\n",
    "root.right.right = Node(7)\n",
    "root.left.left = Node(4)\n",
    "root.left.right = Node(5)\n",
    "TreeLevelPrint(root)"
   ]
  },
  {
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}