TREES.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e0e2bd5a",
   "metadata": {},
   "source": [
    "# Tree Representation Implementation\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "c2cf3319",
   "metadata": {},
   "outputs": [],
   "source": [
    "def BinaryTree(r):\n",
    "    return [r,[],[]]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "4acf61b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertLeft(root, newBranch):\n",
    "    t = root.pop(1)\n",
    "    \n",
    "    if len(t) > 1:\n",
    "        root.insert(1,[newBranch,t,[]])\n",
    "    else:\n",
    "        root.insert(1,[newBranch,[],[]])\n",
    "        \n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "c7d7f754",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertRight(root, newBranch):\n",
    "    t = root.pop(2)\n",
    "    \n",
    "    if len(t) > 1:\n",
    "        root.insert(2,[newBranch,[],t])\n",
    "    else:\n",
    "        root.insert(2,[newBranch,[],[]])\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "88248399",
   "metadata": {},
   "outputs": [],
   "source": [
    "def getRootValue(root):\n",
    "    return root[0]\n",
    "\n",
    "def setRootValue(root, newValue):\n",
    "    root[0] = newValue\n",
    "    \n",
    "def getLeftChild(root):\n",
    "    return root[1]\n",
    "\n",
    "def getRightChild(root):\n",
    "    return root[2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "9fd38009",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, [[9, 22, 66, 55], [[8, 11], [7, [], []], []], []], []]\n"
     ]
    }
   ],
   "source": [
    "r = BinaryTree(3)\n",
    "\n",
    "insertLeft(r,7)\n",
    "insertLeft(r,[8,11])\n",
    "insertLeft(r,[9,22,66,55])\n",
    "\n",
    "print(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "859e5293",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, [9, [8, [7, [], []], []], []], [2, [], [1, [], [0, [], []]]]]\n"
     ]
    }
   ],
   "source": [
    "insertRight(r,0)\n",
    "insertRight(r,1)\n",
    "insertRight(r,2)\n",
    "\n",
    "print(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "03b65dbe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "print(getRootValue(r))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "017d1da1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, [8, [7, [], []], []], []]\n"
     ]
    }
   ],
   "source": [
    "print(getLeftChild(r))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "486a4f6c",
   "metadata": {},
   "source": [
    "# Node and References Implementation a Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "ff92c64f",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree():\n",
    "    \n",
    "    def __init__(self, rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftchild = None\n",
    "        self.rightchild = None\n",
    "        \n",
    "    def insertLeft(self, newNode):\n",
    "        \n",
    "        if self.leftchild == None:\n",
    "            self.leftchild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.leftchild = self.leftchild\n",
    "            self.leftchild = t\n",
    "    \n",
    "    def insertRight(self, newNode):\n",
    "        \n",
    "        if self.rightchild == None:\n",
    "            self.rightchild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.rightchild = self.rightchild\n",
    "            self.rightchild = t\n",
    "            \n",
    "    def getRightChild(self):\n",
    "        return self.rightchild\n",
    "    \n",
    "    def getLeftChild(self):\n",
    "        return self.leftchild\n",
    "    \n",
    "    def setRootValue(self, value):\n",
    "        self.key = value\n",
    "        \n",
    "    def getRootValue(self):\n",
    "        return self.key\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "67ae9d1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "r = BinaryTree(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "e05a0c10",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\n"
     ]
    }
   ],
   "source": [
    "r.insertLeft(\"b\")\n",
    "\n",
    "print(r.leftchild.key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "a12ffd44",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "print(r.getRootValue())\n",
    "print(r.getRightChild())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7aeb3d12",
   "metadata": {},
   "source": [
    "# Tree Traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f2d777e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTreeTraversal(object):\n",
    "    \n",
    "    def __init__(self,value):\n",
    "        self.value = value\n",
    "        self.leftchild = None\n",
    "        self.rightchild = None\n",
    "        \n",
    "    def insertLeft(self,newNode):\n",
    "        \n",
    "        if self.leftchild == None:\n",
    "            self.leftchild = BinaryTreeTraversal(newNode)\n",
    "            \n",
    "        else:            \n",
    "            temp = BinaryTreeTraversal(newNode)\n",
    "            temp.leftchild = self.leftchild\n",
    "            self.leftchild = temp\n",
    "    def insertRight(self, newNode):\n",
    "        \n",
    "        if self.rightchild == None:\n",
    "            self.rightchild = BinaryTreeTraversal(newNode)\n",
    "        else:\n",
    "            temp = BinaryTreeTraversal(newNode)\n",
    "            temp.rightchild = self.rightchild\n",
    "            self.rightchild = temp\n",
    "            \n",
    "    def getRootVal(self):\n",
    "        return self.value\n",
    "    \n",
    "    def getLeftChild(self):\n",
    "        return self.leftchild\n",
    "    \n",
    "    def getRightChild(self):\n",
    "        return self.rightchild\n",
    "    \n",
    "    def preOrder(self):\n",
    "        print(self.value)\n",
    "        if self.leftchild:\n",
    "            self.leftchild.preOrder()\n",
    "        if self.rightchild:\n",
    "            self.rightchild.preOrder()\n",
    "    def postOrder(self):\n",
    "        if self.leftchild:\n",
    "            self.leftchild.postOrder()\n",
    "        \n",
    "        if self.rightchild:\n",
    "            self.rightchild.postOrder()\n",
    "            \n",
    "        print(self.value)\n",
    "        \n",
    "    def inOrder(self):\n",
    "        if self.leftchild:\n",
    "            self.leftchild.inOrder()\n",
    "            \n",
    "        print(self.value)\n",
    "        \n",
    "        if self.rightchild:\n",
    "            self.rightchild.inOrder()\n",
    "       \n",
    "        \n",
    "        \n",
    "def preOrder(tree):\n",
    "    #Root --> Left --> Right\n",
    "    if tree:\n",
    "        print(tree.getRootVal())\n",
    "        preOrder(tree.getLeftChild())\n",
    "        preOrder(tree.getRightChild())\n",
    "    \n",
    "def postOrder(tree):\n",
    "    #Left --> Right --> Root\n",
    "    if tree != None:\n",
    "        postOrder(tree.getLeftChild())\n",
    "        postOrder(tree.getRightChild())\n",
    "        print(tree.getRootVal())\n",
    "        \n",
    "def inOrder(tree):\n",
    "    #Left -- > Root --> Right\n",
    "    \n",
    "    if tree != None:\n",
    "        inOrder(tree.getLeftChild())\n",
    "        print(tree.getRootVal())\n",
    "        inOrder(tree.getRightChild())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d3b0c5c8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "7\n",
      "10\n",
      "9\n",
      "1\n",
      "7\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "r = BinaryTreeTraversal(6)\n",
    "r.insertLeft(7)\n",
    "r.insertRight(1)\n",
    "r.leftchild.insertLeft(10)\n",
    "r.leftchild.insertRight(9)\n",
    "\n",
    "r.rightchild.insertLeft(7)\n",
    "r.rightchild.insertRight(2)\n",
    "r.rightchild.rightchild.insertRight(4)\n",
    "r.rightchild.rightchild.insertLeft(3)\n",
    "\n",
    "preOrder(r)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "14f52a8a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "7\n",
      "10\n",
      "9\n",
      "1\n",
      "7\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "\n",
    "r = BinaryTreeTraversal(6)\n",
    "\n",
    "r.leftchild = BinaryTreeTraversal(7)\n",
    "\n",
    "r.leftchild.leftchild = BinaryTreeTraversal(10)\n",
    "r.leftchild.rightchild = BinaryTreeTraversal(9)\n",
    "\n",
    "r.rightchild = BinaryTreeTraversal(1)\n",
    "r.rightchild.leftchild = BinaryTreeTraversal(7)\n",
    "r.rightchild.rightchild = BinaryTreeTraversal(2)\n",
    "r.rightchild.rightchild.rightchild = BinaryTreeTraversal(4)\n",
    "r.rightchild.rightchild.leftchild = BinaryTreeTraversal(3)\n",
    "\n",
    "\n",
    "preOrder(r)\n",
    "\n",
    "              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "7006a72d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "7\n",
      "10\n",
      "9\n",
      "1\n",
      "7\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "r.preOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "44792b8a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "9\n",
      "7\n",
      "7\n",
      "3\n",
      "4\n",
      "2\n",
      "1\n",
      "6\n",
      "10\n",
      "9\n",
      "7\n",
      "7\n",
      "3\n",
      "4\n",
      "2\n",
      "1\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "postOrder(r)\n",
    "r.postOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "0c076c4d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "7\n",
      "9\n",
      "6\n",
      "7\n",
      "1\n",
      "3\n",
      "2\n",
      "4\n",
      "10\n",
      "7\n",
      "9\n",
      "6\n",
      "7\n",
      "1\n",
      "3\n",
      "2\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "inOrder(r)\n",
    "r.inOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "018d1e98",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "7\n",
      "9\n",
      "22\n",
      "6\n",
      "7\n",
      "1\n",
      "3\n",
      "2\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "r.insertLeft(22)\n",
    "r.inOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "84fe0fce",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "7\n",
      "9\n",
      "22\n",
      "6\n",
      "33\n",
      "7\n",
      "1\n",
      "3\n",
      "2\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "r.insertRight(33)\n",
    "r.inOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "a3687d84",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "7\n",
      "9\n",
      "22\n",
      "44\n",
      "6\n",
      "33\n",
      "7\n",
      "1\n",
      "3\n",
      "2\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "r.insertLeft(44)\n",
    "r.inOrder()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8fcfd4a",
   "metadata": {},
   "source": [
    "# Binary Heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "b69742f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Min Heap\n",
    "\n",
    "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": "code",
   "execution_count": 22,
   "id": "2b44d536",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 3, 2, 6, 5, 8, 4]\n",
      "[0, 1, 2, 2, 3, 5, 8, 4, 6]\n",
      "[0, 2, 2, 4, 3, 5, 8, 6]\n"
     ]
    }
   ],
   "source": [
    "r = BinHeap()\n",
    "r.buildHeap([5,6,8,1,3,2,4])\n",
    "print(r.heapList)\n",
    "r.insert(2)\n",
    "print(r.heapList)\n",
    "r.delMin()\n",
    "print(r.heapList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3cb51152",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryHeap:\n",
    "    def __init__(self):\n",
    "        self.heaplist = [0]\n",
    "        self.currentsize = 0\n",
    "        \n",
    "    def buildHeap(self, alist):\n",
    "        self.heaplist = [0] + alist[:]\n",
    "        self.currentsize = 0 + len(alist)\n",
    "        i = len(alist) // 2\n",
    "        while (i>0):\n",
    "            self.percDown(i)\n",
    "            i -= 1\n",
    "        \n",
    "        \n",
    "    def percDown(self, i):\n",
    "                \n",
    "        while (i*2+1 <= self.currentsize):\n",
    "            mc = self.minChild(i)\n",
    "            \n",
    "            if self.heaplist[i] > self.heaplist[mc]:\n",
    "                temp = self.heaplist[i]\n",
    "                self.heaplist[i] = self.heaplist[mc]\n",
    "                self.heaplist[mc] = temp\n",
    "            \n",
    "            i = mc  # Stop while loop\n",
    "            print(i)\n",
    "    def minChild(self, i):\n",
    "        \n",
    "        if i * 2 + 1 > self.currentsize:\n",
    "            return i * 2\n",
    "        \n",
    "        else:\n",
    "            if self.heaplist[i*2+1] > self.heaplist[i*2]:\n",
    "                return i*2\n",
    "            else:\n",
    "                return i*2+1\n",
    "            \n",
    "    def insert(self, value):\n",
    "        self.heaplist.append(value)\n",
    "        self.currentsize += 1\n",
    "        self.percUp(self.currentsize)\n",
    "        \n",
    "    def percUp(self, i):\n",
    "        while i//2 > 0:\n",
    "            if self.heaplist[i] < self.heaplist[i//2]:\n",
    "                temp = self.heaplist[i//2]\n",
    "                self.heaplist[i//2]=self.heaplist[i]\n",
    "                self.heaplist[i] = temp\n",
    "                \n",
    "            i = i//2\n",
    "    def delMin(self):\n",
    "        root = self.heaplist[1]\n",
    "        self.heaplist[1] = self.heaplist[self.currentsize]\n",
    "        self.heaplist.pop()\n",
    "        self.currentsize -= 1\n",
    "        self.percDown(1)\n",
    "        return root\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a3ed538",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = BinaryHeap()\n",
    "a.buildHeap([5,6,8,1,3,2,4])\n",
    "print(a.heaplist)\n",
    "a.insert(2)\n",
    "print(a.heaplist)\n",
    "a.delMin()\n",
    "print(a.heaplist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9c807da4",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Max Heap\n",
    "\n",
    "class MaxHeap(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        \n",
    "        self.heaplist = [0]\n",
    "        self.currentsize = 0\n",
    "        \n",
    "    def buildHeap(self, list):\n",
    "        \n",
    "        self.heaplist = [0] + list[:]\n",
    "        self.currentsize = 0 + len(list)\n",
    "        i = len(list) // 2\n",
    "        \n",
    "        while i > 0:\n",
    "            self.percDown(i)\n",
    "            i -= 1\n",
    "            \n",
    "    def percDown(self, i):\n",
    "        \n",
    "        while (i*2+1 <= self.currentsize):\n",
    "            maxchild = self.maxChild(i)\n",
    "            if self.heaplist[i] < self.heaplist[maxchild]:\n",
    "                temp = self.heaplist[i]\n",
    "                self.heaplist[i] = self.heaplist[maxchild]\n",
    "                self.heaplist[maxchild] = temp\n",
    "            i = maxchild \n",
    "            \n",
    "    def maxChild(self, i):\n",
    "        \n",
    "        if self.heaplist[i*2+1] > self.heaplist[i*2]:\n",
    "            return i*2+1\n",
    "        else:\n",
    "            return i*2\n",
    "        \n",
    "    def delMax(self):\n",
    "        temp = self.heaplist[1]\n",
    "        self.heaplist[1] = self.heaplist[self.currentsize]\n",
    "        self.currentsize -= 1\n",
    "        self.heaplist.pop()\n",
    "        self.percDown(1)\n",
    "        \n",
    "    def insert(self , value):\n",
    "        self.currentsize += 1\n",
    "        self.heaplist.append(value)\n",
    "        self.percUp(self.currentsize)\n",
    "        \n",
    "    def percUp(self, i):\n",
    "        \n",
    "        while i // 2 > 0:\n",
    "            if self.heaplist[i//2] < self.heaplist[i]:\n",
    "                temp = self.heaplist[i//2]\n",
    "                self.heaplist[i//2] = self.heaplist[i]\n",
    "                self.heaplist[i] = temp\n",
    "            i -= 1\n",
    "                \n",
    "            \n",
    "        \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c153a780",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 8, 6, 5, 1, 3, 2, 4]\n"
     ]
    }
   ],
   "source": [
    "b = MaxHeap()\n",
    "b.buildHeap([5,6,8,1,3,2,4])\n",
    "print(b.heaplist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "4818837f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 6, 4, 5, 1, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "b.delMax()\n",
    "print(b.heaplist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4e887814",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 7, 4, 6, 1, 3, 2, 5]\n"
     ]
    }
   ],
   "source": [
    "b.insert(7)\n",
    "print(b.heaplist)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e2b481b",
   "metadata": {},
   "source": [
    "# Binary Search Tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 264,
   "id": "3834818b",
   "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\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",
    "    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",
    "        \n",
    "    def __delitem__(self,key):\n",
    "        \n",
    "        self.delete(key)\n",
    "\n",
    "    def spliceOut(self, succ):\n",
    "        if succ.isLeaf():\n",
    "            if succ.isLeftChild():\n",
    "                \n",
    "                succ.parent.leftChild = None\n",
    "            else:\n",
    "                succ.parent.rightChild = None\n",
    "        elif succ.hasAnyChildren():\n",
    "            if succ.hasRightChild():\n",
    "                \n",
    "                if succ.isLeftChild():\n",
    "                    \n",
    "                    succ.parent.leftChild = succ.rightChild\n",
    "                    succ.rightChild.parent = succ.parent\n",
    "                else:\n",
    "                    \n",
    "                    succ.parent.rightChild = succ.rightChild\n",
    "                    succ.rightChild.parent = succ.parent\n",
    "\n",
    "\n",
    "    def findSuccessor(self, currentNode):\n",
    "\n",
    "        succ = currentNode\n",
    "        if currentNode.hasRightChild():\n",
    "            succ = self.findMin(currentNode.rightChild)\n",
    "        #else:\n",
    "         #   if currentNode.parent:\n",
    "                \n",
    "          #      if currentNode.isLeftChild():\n",
    "                    \n",
    "           #         succ = currentNode.parent\n",
    "            #    else:\n",
    "             #       currentNode.parent.rightChild = None\n",
    "              #      succ = currentNode.parent.findSuccessor()\n",
    "               #     currentNode.parent.rightChild = currentNode\n",
    "        return succ\n",
    "    \n",
    "    def findMin(self, currentNode):\n",
    "        \n",
    "        current = currentNode\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",
    "                \n",
    "           # This node has both children\n",
    "        elif currentNode.hasBothChildren(): #interior\n",
    "            \n",
    "            succ = self.findSuccessor(currentNode)\n",
    "            self.spliceOut(succ)\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",
    "    def __iter__(self):\n",
    "        if self:\n",
    "            if self.hasLeftChild():\n",
    "                for elem in self.leftChild:\n",
    "                    yield elem\n",
    "            yield self.key\n",
    "            if self.hasRightChild():\n",
    "                for elem in self.rightChild:\n",
    "                    yield elem\n",
    "            yield self.key\n",
    "               \n",
    "    def printTree(self):\n",
    "        print(self._print(self.root))\n",
    "             \n",
    "    def _print(self, currentNode):\n",
    "        count = []\n",
    "        if currentNode != None:\n",
    "            \n",
    "            if currentNode.hasRightChild():\n",
    "                count.append(currentNode.key)\n",
    "                return self._print(currentNode.rightChild)\n",
    "      \n",
    "            elif currentNode.hasLeftChild():\n",
    "                count.append(currentNode.key)\n",
    "                return self._print(currentNode.leftChild)\n",
    "            \n",
    "            else: \n",
    "                return currentNode.key\n",
    "\n",
    "    \n",
    "        \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 265,
   "id": "8a3dc67b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "mytree = BinarySearchTree()\n",
    "mytree[50] = \"a\"\n",
    "mytree[45]=\"b\"\n",
    "mytree[60]=\"c\"\n",
    "mytree[55]=\"d\"\n",
    "mytree.put(70,\"e\")\n",
    "mytree.put(56,\"f\")\n",
    "mytree.put(58,\"g\")\n",
    "mytree.put(65,\"h\")\n",
    "mytree.put(80,\"j\")\n",
    "mytree.put(40,\"k\")\n",
    "mytree.put(30,\"l\")\n",
    "mytree.put(43,\"p\")\n",
    "mytree.put(48,\"o\")\n",
    "mytree.put(47,\"w\")\n",
    "mytree.put(46,\"s\")\n",
    "mytree.put(49,\"z\")\n",
    "mytree.put(66,\"x\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "id": "77764321",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "60\n",
      "45\n",
      "40\n",
      "48\n"
     ]
    }
   ],
   "source": [
    "print(mytree.get(10))\n",
    "print(mytree.root.rightChild.key)\n",
    "print(mytree.root.leftChild.key)\n",
    "print(mytree.root.leftChild.leftChild.key)\n",
    "print(mytree.root.leftChild.rightChild.key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 267,
   "id": "a8030b41",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<generator object BinarySearchTree.__iter__ at 0x0000025697BE4510>\n"
     ]
    }
   ],
   "source": [
    "a = mytree.__iter__()\n",
    "print(a.__iter__())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 268,
   "id": "fe5890ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "\n",
    "mytree.delete(50)\n",
    "print(mytree.root.key)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c38a2871",
   "metadata": {},
   "source": [
    "# Check BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "58e80869",
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, key, value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "class Solution:\n",
    "    \n",
    "    def isValidBST(self, root):\n",
    "                 \n",
    "        def verify(root, left, right):\n",
    "            if not root:\n",
    "                return True\n",
    "            if not( left < root.key < right ):\n",
    "                return False\n",
    "            return (verify(root.left, left, root.key) and verify(root.right, root.key, right))\n",
    "        \n",
    "        return verify(root, float(\"-inf\"), float(\"inf\"))\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "a9ab1705",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "root = TreeNode(50, \"a\")\n",
    "root.right = TreeNode(60,\"b\")\n",
    "root.left = TreeNode(45,\"c\")\n",
    "root.right.right = TreeNode(70,\"d\")\n",
    "root.right.left = TreeNode(55,\"e\")\n",
    "a = Solution()\n",
    "print(a.isValidBST(root))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a2e5bb7",
   "metadata": {},
   "source": [
    "print(float(\"inf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "bbbf9861",
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, key, value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "class Solution:\n",
    "    def tree_max(self, node):\n",
    "        if not node:\n",
    "            return float(\"-inf\")\n",
    "        max_left = self.tree_max(node.left)\n",
    "        max_right = self.tree_max(node.right)\n",
    "        return max(node.key, max_left, max_right)\n",
    "    def tree_min(self, node):\n",
    "        if not node:\n",
    "            return float(\"inf\")\n",
    "        min_left = self.tree_min(node.left)\n",
    "        min_right = self.tree_min(node.right)\n",
    "        return min(node.key, min_left, min_right)\n",
    "    \n",
    "    def verify(self, node):\n",
    "        if not node:\n",
    "            return True\n",
    "        if (self.tree_max(node.left) <= node.key <= self.tree_min(node.right) and verify(node.left) and verify(node.right)):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "54765db8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "root = TreeNode(50, \"a\")\n",
    "root.right = TreeNode(60,\"b\")\n",
    "root.left = TreeNode(45,\"c\")\n",
    "root.right.right = TreeNode(70,\"d\")\n",
    "root.right.left = TreeNode(55,\"e\")\n",
    "a = Solution()\n",
    "print(a.verify(root))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a30e115",
   "metadata": {},
   "source": [
    "# Tree Level Order Print\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "cbe21066",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, key, value, right = None, left = None ):   \n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.right = right\n",
    "        self.left = left \n",
    "        \n",
    "class Solution:\n",
    "    def levelOrder(self, root):\n",
    "        \n",
    "        res = []\n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "        \n",
    "        while que:\n",
    "            level = [] \n",
    "            for i in range(len(que)):\n",
    "                node = que.popleft()\n",
    "                if node:\n",
    "                    level.append(node.key)\n",
    "                    que.append(node.left)\n",
    "                    que.append(node.right)\n",
    "            if level:      \n",
    "                res.append(level)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "559a6421",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[50], [45, 60], [55, 70], []]\n"
     ]
    }
   ],
   "source": [
    "root = TreeNode(50, \"a\")\n",
    "root.right = TreeNode(60,\"b\")\n",
    "root.left = TreeNode(45,\"c\")\n",
    "root.right.right = TreeNode(70,\"d\")\n",
    "root.right.left = TreeNode(55,\"e\")\n",
    "a = Solution()\n",
    "print(a.levelOrder(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "6f12dd68",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, key, value, right = None, left = None ):   \n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.right = right\n",
    "        self.left = left \n",
    "        \n",
    "    def levelOrderTree(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        nodes = collections.deque()\n",
    "        nodes.append(root)\n",
    "        current_count = 1\n",
    "        next_count = 0\n",
    "        \n",
    "        while len(nodes):\n",
    "            currentNode = nodes.popleft() #len(nodes)-1 \n",
    "            current_count -= 1\n",
    "            \n",
    "            print(currentNode.key, end = \" \"),\n",
    "            \n",
    "            if currentNode.left:\n",
    "                nodes.append(currentNode.left)\n",
    "                next_count += 1\n",
    "                \n",
    "            if currentNode.right:\n",
    "                nodes.append(currentNode.right)\n",
    "                next_count += 1 \n",
    "                \n",
    "            if current_count == 0:\n",
    "                print(\"\\n\")\n",
    "                current_count, next_count = next_count, current_count\n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "607213c3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "50 \n",
      "\n",
      "45 60 \n",
      "\n",
      "100 90 80 70 \n",
      "\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "root = TreeNode(50, \"a\")\n",
    "root.right = TreeNode(60,\"b\")\n",
    "root.left = TreeNode(45,\"c\")\n",
    "root.right.right = TreeNode(70,\"d\")\n",
    "root.right.left = TreeNode(80,\"d\")\n",
    "root.left.right = TreeNode(90,\"d\")\n",
    "root.left.left = TreeNode(100,\"d\")\n",
    "root.levelOrderTree(root)\n",
    "\n",
    "nodes1 = collections.deque([root])\n",
    "print(len(nodes1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "2209ff1a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "deque([12, 3, 4, 5])\n",
      "12\n",
      "deque([3, 4, 5])\n"
     ]
    }
   ],
   "source": [
    "import collections\n",
    "que = collections.deque([1,12,3,4,5])\n",
    "print(que.popleft())\n",
    "print(que)\n",
    "print(que.popleft())\n",
    "print(que)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e591aef8",
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.right = None\n",
    "        self.left = None\n",
    "class Solution:\n",
    "    def levelOrder(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        ans = []\n",
    "        prev_queue = [root]\n",
    "        queue = prev_queue\n",
    "        while queue:\n",
    "            queue = []\n",
    "            level = []\n",
    "            for curr in prev_queue:\n",
    "                level.append(curr.val)\n",
    "                if curr.left:\n",
    "                    queue.append(curr.left)\n",
    "                if curr.right:\n",
    "                    queue.append(curr.right)\n",
    "            ans.append(level)\n",
    "            prev_queue = queue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "953713db",
   "metadata": {},
   "outputs": [],
   "source": [
    "mytree = TreeNode(8)\n",
    "mytree.left = TreeNode(3)\n",
    "mytree.right = TreeNode(10)\n",
    "mytree.right.right = TreeNode(14)\n",
    "mytree.right.right.left = TreeNode(13)\n",
    "mytree.left.right = TreeNode(6)\n",
    "mytree.left.left = TreeNode(1)\n",
    "mytree.left.right.left = TreeNode(4)\n",
    "mytree.left.right.right = TreeNode(7)\n",
    "solu = Solution()\n",
    "print(solu.levelOrder(mytree))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "250d57cd",
   "metadata": {},
   "source": [
    "# TRIM A BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "d5038668",
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.right = None\n",
    "        self.left = None\n",
    "\n",
    "def trimBST(tree, minVal, maxVal):\n",
    "    \n",
    "    if not tree:\n",
    "        return \n",
    "    \n",
    "    tree.left = trimBST(tree.left, minVal, maxVal)\n",
    "    tree.right = trimBST(tree.right, minVal, maxVal)  \n",
    "    \n",
    "    if minVal <= tree.val <= maxVal:\n",
    "        return tree\n",
    "    \n",
    "    if tree.val < minVal:\n",
    "        return tree.right\n",
    "    \n",
    "    if tree.val > maxVal:\n",
    "        return tree.left  \n",
    "        \n",
    "\n",
    "\n",
    "    \n",
    "def levelOrder(root):\n",
    "        \n",
    "    res = []\n",
    "    que = collections.deque([root])\n",
    "   \n",
    "        \n",
    "    while que:\n",
    "        level = [] \n",
    "        for i in range(len(que)):\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                level.append(node.val)\n",
    "                que.append(node.left)\n",
    "                que.append(node.right)\n",
    "                  \n",
    "        if level:\n",
    "            res.append(level)\n",
    "    return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "582d19c0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[8], [6, 10], [7, 13]]\n"
     ]
    }
   ],
   "source": [
    "mytree = TreeNode(8)\n",
    "mytree.left = TreeNode(3)\n",
    "mytree.right = TreeNode(10)\n",
    "mytree.right.right = TreeNode(14)\n",
    "mytree.right.right.left = TreeNode(13)\n",
    "mytree.left.right = TreeNode(6)\n",
    "mytree.left.left = TreeNode(1)\n",
    "mytree.left.right.left = TreeNode(4)\n",
    "mytree.left.right.right = TreeNode(7)\n",
    "trimBST(mytree, 5, 13)\n",
    "print(levelOrder(mytree))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "41822adf",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "class TreeNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "def trimBST(tree, minVal, maxVal):\n",
    "    if not tree:\n",
    "        return \n",
    "    \n",
    "    tree.left = trimBST(tree.left, minVal, maxVal)\n",
    "    tree.right = trimBST(tree.right, minVal, maxVal)\n",
    "    \n",
    "    if minVal <= tree.val <= maxVal:\n",
    "        return tree\n",
    "    if tree.val < minVal:\n",
    "        return tree.right\n",
    "    if tree.val > maxVal:\n",
    "        return tree.left\n",
    "    \n",
    "def levelOrderTree(root):\n",
    "    res = []\n",
    "    que = collections.deque()\n",
    "    que.append(root)\n",
    "    \n",
    "    for i in range(len(que)):\n",
    "        temp = []\n",
    "        node = que.popleft()\n",
    "        if node:\n",
    "            temp.append(node.val)\n",
    "            que.append(node.left)\n",
    "            que.append(node.right)\n",
    "    if temp:\n",
    "        res.append(temp)\n",
    "    return res\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "49b292fa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[8], [6, 10], [7, 13]]\n"
     ]
    }
   ],
   "source": [
    "mytree = TreeNode(8)\n",
    "mytree.left = TreeNode(3)\n",
    "mytree.right = TreeNode(10)\n",
    "mytree.right.right = TreeNode(14)\n",
    "mytree.right.right.left = TreeNode(13)\n",
    "mytree.left.right = TreeNode(6)\n",
    "mytree.left.left = TreeNode(1)\n",
    "mytree.left.right.left = TreeNode(4)\n",
    "mytree.left.right.right = TreeNode(7)\n",
    "trimBST(mytree, 5, 13)\n",
    "print(levelOrder(mytree))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3c9144ad",
   "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": 5
}