{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "23319a6a",
   "metadata": {},
   "source": [
    "# Module 2, Extra exercises\n",
    "\n",
    "Find below random exercises to practice more with the sorting and the data structures we have seen during the practical lessons. Solutions will be provided in a few days."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f11d363f",
   "metadata": {},
   "source": [
    "## Class Definitions (BinaryTree and DiGraphLL)\n",
    "These classes are provided for the exercises."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a5d25a75",
   "metadata": {},
   "outputs": [],
   "source": [
    "# BinaryTree class\n",
    "class BinaryTree:\n",
    "    def __init__(self, value):\n",
    "        self.__data = value\n",
    "        self.__right = None\n",
    "        self.__left = None\n",
    "        self.__parent = None\n",
    "\n",
    "    def getValue(self):\n",
    "        return self.__data\n",
    "    def setValue(self, newValue):\n",
    "        self.__data = newValue\n",
    "\n",
    "    def getParent(self):\n",
    "        return self.__parent\n",
    "    def setParent(self, tree):\n",
    "        self.__parent = tree\n",
    "\n",
    "    def getRight(self):\n",
    "        return self.__right\n",
    "    def getLeft(self):\n",
    "        return self.__left\n",
    "\n",
    "    def insertRight(self, tree):\n",
    "        if self.__right == None:\n",
    "            self.__right = tree\n",
    "            tree.setParent(self)\n",
    "\n",
    "    def insertLeft(self, tree):\n",
    "        if self.__left == None:\n",
    "            self.__left = tree\n",
    "            tree.setParent(self)\n",
    "\n",
    "    def deleteRight(self):\n",
    "        self.__right = None\n",
    "\n",
    "    def deleteLeft(self):\n",
    "        self.__left = None\n",
    "\n",
    "def printTree(root):\n",
    "    cur = root\n",
    "    #each element is a node and a depth\n",
    "    #depth is used to format prints (with tabs)\n",
    "    nodes = [(cur,0)]\n",
    "    tabs = \"\"\n",
    "    lev = 0\n",
    "    while len(nodes) >0:\n",
    "        cur, lev = nodes.pop(-1)\n",
    "        #print(\"{}{}\".format(\"\\t\"*lev, cur.getValue()))\n",
    "        if cur.getRight() != None:\n",
    "            print (\"{}{} (r)-> {}\".format(\"\\t\"*lev,\n",
    "                                          cur.getValue(),\n",
    "                                          cur.getRight().getValue()))\n",
    "            nodes.append((cur.getRight(), lev+1))\n",
    "        if cur.getLeft() != None:\n",
    "            print (\"{}{} (l)-> {}\".format(\"\\t\"*lev,\n",
    "                                          cur.getValue(),\n",
    "                                          cur.getLeft().getValue()))\n",
    "            nodes.append((cur.getLeft(), lev+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "70834b89",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Directed graph class\n",
    "class DiGraphLL:\n",
    "    def __init__(self):\n",
    "        self.nodes = dict()\n",
    "\n",
    "    def insertNode(self, node):\n",
    "        test = self.nodes.get(node, None)\n",
    "\n",
    "        if test == None:\n",
    "            self.nodes[node] = {}\n",
    "\n",
    "    def insertEdge(self, node1, node2, weight):\n",
    "        test = self.nodes.get(node1, None)\n",
    "        test1 = self.nodes.get(node2, None)\n",
    "        if test != None and test1 != None:\n",
    "            test = self.nodes[node1].get(node2, None)\n",
    "            if test != None:\n",
    "                exStr= \"Edge {} --> {} already existing.\".format(node1,node2)\n",
    "                raise Exception(exStr)\n",
    "            else:\n",
    "                self.nodes[node1][node2] = weight\n",
    "\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.nodes)\n",
    "\n",
    "    def nodes(self):\n",
    "        return list(self.nodes.keys())\n",
    "\n",
    "    def graph(self):\n",
    "        return self.nodes\n",
    "\n",
    "    def __str__(self):\n",
    "        ret = \"\"\n",
    "        for n in self.nodes:\n",
    "            for edge in self.nodes[n]:\n",
    "\n",
    "                ret += \"{} -- {} --> {}\\n\".format(str(n),\n",
    "                                                  str(self.nodes[n][edge]),\n",
    "                                                  str(edge))\n",
    "        return ret\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f3d882d",
   "metadata": {},
   "source": [
    "## Exercise 1 — Count the Number of Nodes in a Tree\n",
    "\n",
    "The goal of this exercise is to understand how to traverse a binary tree both recursively and iteratively. You are asked to implement a method in the BinaryTree class that returns the total number of nodes in the subtree rooted at the current node using recursion. Then, implement a second version that computes the same value without using recursion, relying instead on an explicit stack or queue. Both methods should return the same result when tested.\n",
    "\n",
    "Implement recursive and iterative versions:\n",
    "\n",
    "```\n",
    "def countNodes(self):\n",
    "    pass\n",
    "\n",
    "def countNodes_iter(self):\n",
    "    pass\n",
    "```\n",
    "\n",
    "Test if you implemented it right with the code below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17a199f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Autograding test for Exercise 1\n",
    "root = BinaryTree(0)\n",
    "a = BinaryTree(1); b = BinaryTree(2)\n",
    "root.insertLeft(a); root.insertRight(b)\n",
    "\n",
    "try:\n",
    "    assert root.countNodes() == 3\n",
    "    assert root.countNodes_iter() == 3\n",
    "    print('Exercise 1 passed')\n",
    "except Exception as e:\n",
    "    print('Exercise 1 failed:', e)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b572340",
   "metadata": {},
   "source": [
    "## Exercise 2 — Check Whether a Value Exists in the Tree\n",
    "\n",
    "This exercise focuses on searching within a binary tree. You should implement a method that returns True if a given value exists anywhere in the tree, using recursion to traverse the nodes. Then, create a second version that performs the same search without recursion, using an explicit stack or queue to explore the tree. Both versions should correctly identify whether the value is present, even if every node needs to be checked.\n",
    "\n",
    "```\n",
    "def contains(self, value):\n",
    "    pass\n",
    "\n",
    "def contains_iter(self, value):\n",
    "    pass\n",
    "\n",
    "```\n",
    "\n",
    "Test the output with the code below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3cf14b9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = BinaryTree(1)\n",
    "a = BinaryTree(2)\n",
    "b = BinaryTree(3)\n",
    "root.insertLeft(a)\n",
    "root.insertRight(b)\n",
    "\n",
    "print(root.contains(2))       # Expected output: True\n",
    "print(root.contains_iter(5))  # Expected output: False\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df108672",
   "metadata": {},
   "source": [
    "## Exercise 3 — Compute the Height of the Tree\n",
    "\n",
    "Compute the height of a binary tree where a leaf node has height one and an empty subtree has height zero. Implement a recursive method that calculates the height and an iterative method using a stack or queue to track node depth. Both methods should return the same height.\n",
    "\n",
    "Example:\n",
    "A tree with a root node and two children has height 2. Calling the method on the root node should return 2.\n",
    "\n",
    "Template for your code:\n",
    "\n",
    "```\n",
    "def height(self):\n",
    "    pass\n",
    "\n",
    "def height_iter(self):\n",
    "    pass\n",
    "```\n",
    "\n",
    "Example check:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa857aea",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = BinaryTree(0)\n",
    "a = BinaryTree(1)\n",
    "b = BinaryTree(2)\n",
    "root.insertLeft(a)\n",
    "root.insertRight(b)\n",
    "\n",
    "print(root.height())       # Expected output: 2\n",
    "print(root.height_iter())  # Expected output: 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ad03a73",
   "metadata": {},
   "source": [
    "## Exercise 4.1 — Check if a node has a self edge in a Graph\n",
    "\n",
    "Consider the DiGraphLL class provided above.\n",
    "Use this code below to generate the following graph:\n",
    "\n",
    "![](images/grahpEx.png)\n",
    "\n",
    "Code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "cbb1b88f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size is: 7\n",
      "Nodes: {'Node_1': {'Node_2': 2, 'Node_4': 5}, 'Node_2': {'Node_1': 7, 'Node_5': 6}, 'Node_3': {}, 'Node_4': {'Node_5': 15, 'Node_4': 4}, 'Node_5': {}, 'Node_6': {'Node_5': 3, 'Node_6': 2}, 'Node_7': {'Node_7': 4}}\n"
     ]
    }
   ],
   "source": [
    "G = DiGraphLL()\n",
    "for i in range(7):\n",
    "    n = \"Node_{}\".format(i+1)\n",
    "    G.insertNode(n)\n",
    "\n",
    "G.insertEdge(\"Node_2\", \"Node_1\", 7)\n",
    "G.insertEdge(\"Node_1\", \"Node_2\", 2)\n",
    "G.insertEdge(\"Node_1\", \"Node_4\", 5)\n",
    "G.insertEdge(\"Node_2\", \"Node_5\", 6)\n",
    "G.insertEdge(\"Node_6\", \"Node_5\", 3)\n",
    "G.insertEdge(\"Node_4\", \"Node_5\", 15)\n",
    "G.insertEdge(\"Node_6\", \"Node_6\", 2)\n",
    "G.insertEdge(\"Node_7\", \"Node_7\", 4)\n",
    "G.insertEdge(\"Node_4\", \"Node_4\", 4)\n",
    "\n",
    "print(\"Size is: {}\".format(len(G)))\n",
    "print(\"Nodes: {}\".format(G.nodes))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "168ae624",
   "metadata": {},
   "source": [
    "Implement a method called *checkSelfEdge()* in the DiGraphLL class that takes a node as input and returns True if the node has an edge pointing to itself, and False otherwise. Make sure to first verify that the node exists in the graph.\n",
    "\n",
    "Hint: Use the adjacency dictionary to determine if the node has an outgoing edge to itself.\n",
    "\n",
    "```\n",
    "def checkSelfEdge(self, node):\n",
    "    pass\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9d51907d",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "print(\"Check for self edge --> \\n\")\n",
    "print(\"Node_10:\")\n",
    "print(G.checkSelfEdge(\"Node_10\")) #should return \"node not found\"\n",
    "print(\"Node_2:\")\n",
    "print(G.checkSelfEdge(\"Node_2\")) #should return False\n",
    "print(\"Node_6:\")\n",
    "print(G.checkSelfEdge(\"Node_6\")) #should return True\n",
    "print(\"Node_7:\") \n",
    "print(G.checkSelfEdge(\"Node_7\")) #should return True\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c64508f",
   "metadata": {},
   "source": [
    "## Exercise 4.2 — Check if a node is isolated (no edges with other nodes)\n",
    "\n",
    "Implement a method called *isolatedNodes()* in the DiGraphLL class that returns a list of all nodes that are completely isolated from the graph. A node is considered isolated if it has no incoming or outgoing edges to other nodes. Self-loops (edges from the node to itself) should not count as connections: nodes with self-loops are still considered isolated.\n",
    "\n",
    "```\n",
    "def isolatedNodes(self):\n",
    "    pass\n",
    "\n",
    "```\n",
    "\n",
    "Test with:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b4e99d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Isolated nodes:\\n\")\n",
    "print(G.isolatedNodes())\n",
    "\n",
    "assert(G.isolatedNodes() == ['Node_3', 'Node_7'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34f33e3c",
   "metadata": {},
   "source": [
    "## Exercise 5\n",
    "\n",
    "A Binary Search Tree (BST) is a binary tree with the following properties:\n",
    "- The left subtree of a node contains only nodes with values lower than that of the node.\n",
    "- The right subtree of a node contains only nodes with values greater than the node’s.\n",
    "- No duplicate nodes are allowed.\n",
    "\n",
    "Look at the BST implemented in the code chunck below.\n",
    "Please check carefully how the class is implemented since it might slightly differ from the one you have seen during the practical class.\n",
    "The BST structure created by the script is shown below:\n",
    "\n",
    "![](images/BST_extraEx.png)\n",
    "\n",
    "TO DO:\n",
    "We have the BST shown above and a number N. Our task is to find the greatest number (node) in the binary search tree that is less than or equal to N.\n",
    "You are asked to implement the missing method **findLargestSmallerKey(self, N)**\n",
    "\n",
    "This method finds the largest key (value of node, as integer) in the BST that is smaller than N. If such a number doesn’t exist, return -1.\n",
    "\n",
    "**Examples:**\n",
    "Input : N = 24 \\\n",
    "Output : 21 \\\n",
    "(searching for 24 will be like 5->12->21) \\\n",
    "Input : N = 4 \\\n",
    "Output : 3 \\\n",
    "(searching for 4 will be like 5->2->3) \\\n",
    "Input : N = 10 \\\n",
    "Output : 9 \\\n",
    "(searching for 10 will be like 5->12->9) \\\n",
    "\n",
    "**TIPS**: \n",
    "There are two key parts for the algorithm.\n",
    "\n",
    "**Part 1**: traversing the tree \\\n",
    "Starting from the root, for each node we choose its left or its right child as the next step, based on\n",
    "a comparison between that node’s key and N: If the current node holds a key smaller than N, we\n",
    "proceed to its right subtree looking for larger keys. Otherwise, we proceed to its left subtree\n",
    "looking for smaller keys.\n",
    "\n",
    "**Part 2**: finding the key \\\n",
    "During this iteration, when the current key is smaller than N, we store it as our result and keep looking for a larger key that is still smaller than N.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91ddc77d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinarySearchTree:\n",
    "    def __init__(self, value):\n",
    "        self.__data = value\n",
    "        self.__right = None\n",
    "        self.__left = None\n",
    "        self.__parent = None\n",
    "\n",
    "    def getValue(self):\n",
    "        return self.__data\n",
    "    def setValue(self, newValue):\n",
    "        self.__data = newValue\n",
    "\n",
    "    def getParent(self):\n",
    "        return self.__parent\n",
    "    def setParent(self, tree):\n",
    "        self.__parent = tree\n",
    "\n",
    "    def getRight(self):\n",
    "        return self.__right\n",
    "    def getLeft(self):\n",
    "        return self.__left\n",
    "\n",
    "    def insertRight(self, tree):\n",
    "        if self.__right == None:\n",
    "            self.__right = tree\n",
    "            tree.setParent(self)\n",
    "    def insertLeft(self, tree):\n",
    "        if self.__left == None:\n",
    "            self.__left = tree\n",
    "            tree.setParent(self)\n",
    "\n",
    "    # START CODING BELOW HERE:\n",
    "\n",
    "    def findLargestSmallerKey(self, N):\n",
    "\n",
    "        result = -1\n",
    "\n",
    "        #to implement\n",
    "\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "def createBST(intList):\n",
    "    \n",
    "    BST = None\n",
    "    if len(intList) > 0:\n",
    "        BST = BinarySearchTree(intList[0])\n",
    "        for el in intList[1:]:\n",
    "            cur_el = BST\n",
    "            alreadyPresent = False\n",
    "            prev_el = None\n",
    "            while cur_el != None:\n",
    "                prev_el = cur_el\n",
    "                cv = cur_el.getValue()\n",
    "                if  cv > el:\n",
    "                    cur_el = cur_el.getLeft()\n",
    "                elif cv < el:\n",
    "                    cur_el = cur_el.getRight()\n",
    "                else:\n",
    "                    alreadyPresent = True\n",
    "                    break\n",
    "\n",
    "            if not alreadyPresent:\n",
    "                node = BinarySearchTree(el)\n",
    "                node.setParent(prev_el)\n",
    "                if prev_el.getValue() > el:\n",
    "                    prev_el.insertLeft(node)\n",
    "                else:\n",
    "                    prev_el.insertRight(node)\n",
    "\n",
    "    return BST\n",
    "\n",
    "\n",
    "def printTree(root):\n",
    "    cur = root\n",
    "    nodes = [(cur,0)]\n",
    "    tabs = \"\"\n",
    "    lev = 0\n",
    "    while len(nodes) >0:\n",
    "        cur, lev = nodes.pop(-1)\n",
    "        if cur.getRight() != None:\n",
    "            print (\"{}{} (r)-> {}\".format(\"\\t\"*lev,\n",
    "                                          cur.getValue(),\n",
    "                                          cur.getRight().getValue()))\n",
    "            nodes.append((cur.getRight(), lev+1))\n",
    "        if cur.getLeft() != None:\n",
    "            print (\"{}{} (l)-> {}\".format(\"\\t\"*lev,\n",
    "                                          cur.getValue(),\n",
    "                                          cur.getLeft().getValue()))\n",
    "            nodes.append((cur.getLeft(), lev+1))\n",
    "\n",
    "\n",
    "\n",
    "# DO NOT modify code below:\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    inList = [5,2,1,3,12,9,21,19,25]\n",
    "\n",
    "    BST = createBST(inList)\n",
    "\n",
    "    print(\"Tree:\\n\")\n",
    "    printTree(BST)\n",
    "\n",
    "\n",
    "    print(\"\\nGreatest number in the BST that is less than or equal to 24 --> \\n\")\n",
    "\n",
    "    print(BST.findLargestSmallerKey(24))\n",
    "\n",
    "    print(\"\\nGreatest number in the BST that is less than or equal to 4 --> \\n\")\n",
    "\n",
    "    print(BST.findLargestSmallerKey(4))\n",
    "\n",
    "\n",
    "    print(\"\\nGreatest number in the BST that is less than or equal to 10 --> \\n\")\n",
    "\n",
    "    print(BST.findLargestSmallerKey(10))\n",
    "\n",
    "    assert BST.findLargestSmallerKey(24) == 21 , \"It should be 21\"\n",
    "\n",
    "    assert BST.findLargestSmallerKey(4) == 3, \"It should be 3\"\n",
    "\n",
    "    assert BST.findLargestSmallerKey( 10) == 9, \"It should be 9\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ef3193f",
   "metadata": {},
   "source": [
    "## Excerise 6\n",
    "\n",
    "Implement the **sort()** method of the class **PancakeSort** in the code below. \n",
    "\n",
    "To test the implementation use the code below, which is  equipped with a main code that tests the method by sorting the list [7, 5, 10, -11, 3, -4, 99, 1].\n",
    "\n",
    "Imagine you have a stack (**not** the stack data structure) of pancakes of different sizes, and you want to arrange them in order from the largest at the bottom to the smallest at the top. \\\n",
    "Here's how Pancake Sort works:\n",
    "Start with your stack of unsorted pancakes. The stack represents the list of numbers that you want to sort (it is not an actual stack data structure).\n",
    "\n",
    "1. Iterate over the stack of pancakes (list of numbers) starting from the bottom  pancake (end of the list) and going towards the top \t(first pancake). This because at the end of each iteration the biggest pancake (number) will be moved to the bottom of the stack (last position in the list), and we want to reduce the size of the list we work with at each iteration.\n",
    " \t\n",
    "2. At each iteration, identify the biggest pancake (number) and get its position X.\n",
    "\n",
    "3. If the biggest pancake is not already at the top, flip the unsorted stack to move it there (in the first position of the list). This means that you must flip the sub-list that goes from 0 to position X. \t\n",
    "\n",
    "4. Now, flip the entire stack (list) so that the biggest pancake is now at the bottom (end of the list).\n",
    "\n",
    "5. Repeat the process (step 1 to 3), focusing on a smaller stack each time (excluding the pancake you've already sorted, which is now at the end).\n",
    "\n",
    "6. Continue until all pancakes are in order (i.e. when you reach the first position in the list)\n",
    "\n",
    "\n",
    "Keep in mind that with flip we mean to reverse the order of the elements in the list (or sub-list). Below there is an example of how the sorting works:\n",
    "\n",
    "\n",
    "![](images/pancackeSorting.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3f84c3f",
   "metadata": {},
   "outputs": [],
   "source": [
    "class SortingAlgorithm:\n",
    "    def __init__(self, data, verbose = True):\n",
    "        self.data = data\n",
    "        self.comparisons = 0\n",
    "        self.operations = 0\n",
    "        self.verbose = verbose\n",
    "\n",
    "    def getData(self):\n",
    "        return self.data\n",
    "\n",
    "    def getOperations(self):\n",
    "        return self.operations\n",
    "\n",
    "    def getComparisons(self):\n",
    "        return self.comparisons\n",
    "\n",
    "    def sort(self):\n",
    "        raise NotImplementedError\n",
    "\n",
    "class PancakeSort(SortingAlgorithm):\n",
    "\n",
    "    def sort(self):\n",
    "\n",
    "        \"\"\"\n",
    "        Implement the sort method for the Pancake Sort algorithm \n",
    "        \"\"\"\n",
    "        \n",
    "        raise NotImplementedError #remove when implementing method\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    d = [7, 5, 10, -11 ,3, -4, 99, 1]\n",
    "    print(d)\n",
    "    insSorter = PancakeSort(d)\n",
    "    insSorter.sort()\n",
    "    print(d)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "3.10.14",
   "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.10.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}