B_Tree_Implementation_and_Automated_Data_Insertion_(CS4520).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "collapsed_sections": [
        "fczhKfLgWSqh",
        "Q-k_6zNW896S",
        "EzsLpSs8M4_4",
        "jGvBPyLVNX-L",
        "Wf0pNi88nB1A"
      ],
      "authorship_tag": "ABX9TyOmskgyk0b4BjJ+sch4Bmd4",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/manishkolla/B-Tree-Implementation-and-Automated-Data-Insertion/blob/main/B_Tree_Implementation_and_Automated_Data_Insertion_(CS4520).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Project Title: B-Tree Implementation and Automated Data Insertion\n",
        "## CS 4520 Design & Analysis: Algorithms  by Prof. Shiraj Pokharel\n",
        "### Project Done By:\n",
        "1.   Manish Kolla\n",
        "2.   Ashwin Gopalakrishnan\n",
        "\n",
        "#### Input: Data File with index which needs to be converted to BTree\n",
        "#### Output: Converted Btree from Dataset and a user interface to manipulate the Btree\n",
        "##### Manipulations Include\n",
        "1.   Searching\n",
        "2.   Removal\n",
        "3.   Depth First Search (Pre Order, In Order, Post Order)\n",
        "4.   Breadth First Search (Level Order Traversal)\n",
        "5.   Exiting\n",
        "\n",
        "##### Responsibilities\n",
        "\n",
        "###### Manish Kolla:\n",
        "###### Coding: Searching and Insertion code of the Btree which include insert(), insert_non_full(), split_child(), Data File Parsing file(), Pre order, In order, Post Order Traversal, Breath First Search, Printing the BTree, debugging and trying to solve the challenges faced\n",
        "###### Paper: Abstract, Material and Methods, Understanding and history of BTrees, Algorithm Design, IEEE Paper Formating\n",
        "\n",
        "\n",
        "---\n",
        "\n",
        "\n",
        "##### Ashwin Gopalakrishnan:\n",
        "###### Coding: Basic Implementation, Deletion part of the code and balancing the Btree which include delete(),_delete_key_from_node(), _delete_from_child(), _get_predecessor(), _fix_deficiency(), _borrow_from_left_sibling(),_borrow_from_right_sibling(), _merge_with_left_sibling(), _merge_with_right_sibling(), debugging and trying to solve the challenges faced\n",
        "\n",
        "###### Paper: Introduction, Algorithm Design, Critique, IEEE Paper Formating\n",
        "\n",
        "\n",
        "---\n",
        "\n",
        "\n",
        "Challenges Faced:\n",
        "1. Duplication of elements when they are moving from child node to parent node in the split_child()\n",
        "2. Errors in the _fix_deficiency() part of the code when the element is deleted from the leaf, the tree is becoming unbalanced\n",
        "3. Errors in Search(), unable to identify the elements in the leaf accurately\n",
        "4. Problems with the insert_non_null() when all the elements in the node are deleted\n",
        "5. Trying it make it as user-friendly as possible for file()\n"
      ],
      "metadata": {
        "id": "ZLqxdFpSR5uM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Final BTree Code\n"
      ],
      "metadata": {
        "id": "igiL0fdMSAhs"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class BTreeNode:\n",
        "    def __init__(self, minDegree):\n",
        "        self.keys = []\n",
        "        self.children = []\n",
        "        self.leaf = True\n",
        "        self.t = minDegree  # The minimum degree (defines the range for the number of keys)\n",
        "    def split_child(self, childIndex, child):\n",
        "          # Splitting the child into two nodes and moving the part of the child to the parent and removing that from the child\n",
        "          new_node = BTreeNode(child.t)\n",
        "          new_node.leaf = child.leaf\n",
        "          t = child.t\n",
        "\n",
        "          # Give the new node the second half which is t-1 of child's keys and children\n",
        "          new_node.keys = child.keys[t-1:]\n",
        "          child.keys=child.keys[:t-1]\n",
        "          #new_node.keys = child.keys[t - 1:]\n",
        "          if not child.leaf:\n",
        "              new_node.children = child.children[t:]\n",
        "              child.children = child.children[:t]\n",
        "\n",
        "          # Reduce the number of keys in child\n",
        "          child.keys = child.keys[:t]\n",
        "\n",
        "          # As child is split, its parent gets a new child\n",
        "          self.children.insert(childIndex + 1, new_node)\n",
        "          #self.keys.insert(childIndex, new_node.keys[-1])\n",
        "          self.keys.insert(childIndex, new_node.keys.pop(0))\n",
        "          #child.keys.pop(t-1)\n",
        "    def insert_non_full(self, key):\n",
        "      # Determining the insert position in the node's key list\n",
        "        insertPosition = len(self.keys) - 1\n",
        "        if self.leaf:\n",
        "            # Insert the new key into the node's key list if its a leaf\n",
        "            self.keys.append(key)\n",
        "            self.keys.sort()\n",
        "        else:\n",
        "            # Find the child which is going to have the new key if its not the leaf\n",
        "            while insertPosition >= 0 and key < self.keys[insertPosition]:\n",
        "                insertPosition -= 1\n",
        "            insertPosition += 1\n",
        "\n",
        "            # If the child is full which is 2t-1, then split it before inserting\n",
        "            if len(self.children[insertPosition].keys) == 2 * self.t - 1:\n",
        "                self.split_child(insertPosition, self.children[insertPosition])\n",
        "                if key > self.keys[insertPosition]:\n",
        "                    insertPosition += 1\n",
        "            #Recursively insert into the appropriate child\n",
        "            self.children[insertPosition].insert_non_full(key)\n",
        "from collections import deque\n",
        "class BTree:\n",
        "    def __init__(self, t):\n",
        "        self.root = BTreeNode(t)\n",
        "        self.t = t\n",
        "    def insert(self, key):\n",
        "        root = self.root\n",
        "        if len(root.keys) == 2 * self.t - 1:\n",
        "            # If root is full then call the split child and also B-tree grows in height\n",
        "            new_node = BTreeNode(self.t)\n",
        "            new_node.children.insert(0, root)\n",
        "            new_node.leaf = False\n",
        "            new_node.split_child(0, root)\n",
        "            # New node is becoming the new root\n",
        "            self.root = new_node\n",
        "        self.root.insert_non_full(key)\n",
        "    def search(self, searchKey):\n",
        "        node = self.root\n",
        "        while True:\n",
        "            # Check current node keys for searchKey\n",
        "            for i in range(len(node.keys)):\n",
        "                if node.keys[i] == searchKey:\n",
        "                    return True\n",
        "            # Traversal logic if not found in the node\n",
        "            if node.leaf:\n",
        "                break\n",
        "            i = len(node.keys) - 1\n",
        "            while i >= 0 and searchKey < node.keys[i]:\n",
        "                i -= 1\n",
        "            i += 1\n",
        "            # Going to the next child node\n",
        "            node = node.children[i]\n",
        "\n",
        "        return False\n",
        "    def delete(self, key):\n",
        "        if not self.root:\n",
        "            return False\n",
        "\n",
        "        # Call the delete function starting from the root\n",
        "        self._delete(self.root, key)\n",
        "\n",
        "    def _delete(self, node, key):\n",
        "      #if the key is none\n",
        "        if node is None:\n",
        "            return\n",
        "        # Find the index of the key to be deleted\n",
        "        keyIndex = 0\n",
        "        while keyIndex < len(node.keys) and key > node.keys[keyIndex]:\n",
        "            keyIndex += 1\n",
        "\n",
        "        # If the key is present in the current node\n",
        "        if keyIndex < len(node.keys) and key == node.keys[keyIndex]:\n",
        "            #print(f\"Key {key} found in node {node.keys}\")\n",
        "            self._delete_key_from_node(node, key, keyIndex)\n",
        "        else:\n",
        "            # If the key is not present in the current node, determine the child to search\n",
        "            if node.leaf:\n",
        "\n",
        "                # If the node is a leaf and the key is not present, then the key doesn't exist\n",
        "                return False\n",
        "\n",
        "            # Recursively delete the key from the appropriate child\n",
        "            self._delete_from_child(node, key, keyIndex)\n",
        "\n",
        "    def _delete_key_from_node(self, node, key, i):\n",
        "        # Case 1: Key is present in a node and is a leaf node just remove it directly\n",
        "        if node.leaf:\n",
        "            #print(\"YESSSSSSSSSSSSSSSS\")\n",
        "            del node.keys[i]\n",
        "        else:\n",
        "            # Case 2: Key is present in a node and is an internal node\n",
        "            # Replace the key with its predecessor (max value from the left child) and recursively delete the predecessor\n",
        "            predecessor = self._get_predecessor(node, i)\n",
        "            node.keys[i] = predecessor\n",
        "            # Recursively delete predecessor from subtree\n",
        "            self._delete(node.children[i], predecessor)\n",
        "            if key in node.keys:\n",
        "              self._delete_key_from_node(node, key, node.keys.index(key))\n",
        "            else:\n",
        "              #key is deleted\n",
        "              return\n",
        "    def _delete_from_child(self, parentNode, keytoDelete, childIndex):\n",
        "        #print(\"Delete from child\")\n",
        "        # Case 3: Key is not present in a node, and the child has the minimum number of keys\n",
        "        if len(parentNode.children[childIndex].keys) == self.t - 1:\n",
        "            # Perform necessary rotations or merges to ensure that the child has enough keys\n",
        "            self._fix_deficiency(parentNode, childIndex)\n",
        "\n",
        "        # Recursively delete the key from the appropriate child\n",
        "        self._delete(parentNode.children[childIndex], keytoDelete)\n",
        "\n",
        "    def _get_predecessor(self, parentNode, childIndex):\n",
        "        # Helper function to find the predecessor (max value) in the subtree rooted at children[i]\n",
        "        current_node = parentNode.children[childIndex]\n",
        "        while not current_node.leaf:\n",
        "            current_node = current_node.children[-1]\n",
        "        # Return the maximum value which is the predecessor\n",
        "        return current_node.keys[-1]\n",
        "    def _fix_deficiency(self, parentNode, childIndex):\n",
        "      #print(\"DEFICI\")\n",
        "      # Case 1: Borrow a key from the left sibling\n",
        "      if childIndex > 0 and len(parentNode.children[childIndex - 1].keys) > self.t - 1:\n",
        "          #print(\"b_left\")\n",
        "          self._borrow_from_left_sibling(parentNode, childIndex)\n",
        "\n",
        "      # Case 2: Borrow a key from the right sibling\n",
        "      elif childIndex < len(parentNode.children) - 1 and len(parentNode.children[childIndex + 1].keys) > self.t - 1:\n",
        "          #print(\"b_right\")\n",
        "          self._borrow_from_right_sibling(parentNode, childIndex)\n",
        "\n",
        "      # Case 3: Merge with the left sibling which is not required as merging with left node can cause culstering and inaccuracy in btree\n",
        "      elif childIndex > 0:\n",
        "          #print(\"m_left\")\n",
        "          #print(parentNode.keys,parentNode.children, childIndex)\n",
        "          #self._merge_with_left_sibling(parentNode, childIndex)\n",
        "          pass\n",
        "\n",
        "      # Case 4: Merge with the right sibling\n",
        "      elif len(parentNode.children)==0:\n",
        "          #print(\"m_right\")\n",
        "          self._merge_with_right_sibling(parentNode, childIndex)\n",
        "      #Case 5: if there is no deficiency do not have do any changes\n",
        "      else:\n",
        "        return\n",
        "\n",
        "    def _borrow_from_left_sibling(self, parentNode, childIndex):\n",
        "        # Borrow a key from the left sibling and adjust the keys in the nodes\n",
        "        child = parentNode.children[childIndex]\n",
        "        left_sibling = parentNode.children[childIndex - 1]\n",
        "\n",
        "        # Move the key from the left sibling to the parent\n",
        "        child.keys.insert(0, parentNode.keys[childIndex - 1])\n",
        "        parentNode.keys[childIndex - 1] = left_sibling.keys.pop()\n",
        "\n",
        "        # If the child is not a leaf, move the child pointer from the left sibling to the child\n",
        "        if not child.leaf:\n",
        "            child.children.insert(0, left_sibling.children.pop())\n",
        "\n",
        "    def _borrow_from_right_sibling(self, parentNode, childIndex):\n",
        "        # Borrow a key from the right sibling and adjust the keys in the nodes\n",
        "        child = parentNode.children[childIndex]\n",
        "        right_sibling = parentNode.children[childIndex + 1]\n",
        "\n",
        "        # Move the key from the right sibling to the parent\n",
        "        child.keys.append(parentNode.keys[childIndex])\n",
        "        parentNode.keys[childIndex] = right_sibling.keys.pop(0)\n",
        "        #parentNode.keys=parentNode.keys[childIndex].pop()\n",
        "\n",
        "        # If the child is not a leaf, move the child pointer from the right sibling to the child\n",
        "        if not child.leaf:\n",
        "            child.children.append(right_sibling.children.pop(0))\n",
        "\n",
        "    def _merge_with_left_sibling(self, parentNode, childIndex):\n",
        "        # Merge the child with its left sibling, adjusting keys and pointers\n",
        "        if len(parentNode.keys)>=1:\n",
        "          child = parentNode.children[childIndex]\n",
        "          left_sibling = parentNode.children[childIndex - 1]\n",
        "\n",
        "          # Move the key from the parent to the left sibling\n",
        "          left_sibling.keys.append(parentNode.keys.pop(childIndex - 1))\n",
        "\n",
        "          # Move all keys and pointers from the child to the left sibling\n",
        "          left_sibling.keys.extend(child.keys)\n",
        "          left_sibling.children.extend(child.children)\n",
        "\n",
        "          # Remove the child from the parent's keys and children lists\n",
        "          if len(parentNode.keys)>0:\n",
        "            parentNode.keys.pop(childIndex - 1)\n",
        "            parentNode.children.pop(childIndex)\n",
        "        else:\n",
        "          return\n",
        "\n",
        "    def _merge_with_right_sibling(self, parentNode, childIndex):\n",
        "        # Merge the child with its right sibling, adjusting keys and pointers\n",
        "        child = parentNode.children[childIndex]\n",
        "        right_sibling = parentNode.children[childIndex + 1]\n",
        "\n",
        "        # Move the key from the parent to the child\n",
        "        child.keys.append(parentNode.keys.pop(childIndex))\n",
        "\n",
        "        # Move all keys and pointers from the right sibling to the child\n",
        "        child.keys.extend(right_sibling.keys)\n",
        "        child.children.extend(right_sibling.children)\n",
        "\n",
        "        # Remove the right sibling from the parent's keys and children lists\n",
        "        if len(parentNode.keys)>0:\n",
        "          parentNode.keys.pop(childIndex)\n",
        "          parentNode.children.pop(childIndex + 1)\n",
        "    def pre_order_traversal(self):\n",
        "        if self.root:\n",
        "            self._pre_order_traversal(self.root)\n",
        "\n",
        "    def _pre_order_traversal(self, node):\n",
        "        if node:\n",
        "            # Visit the current node\n",
        "            print(node.keys, end=\" \")\n",
        "\n",
        "            # Recursively traverse each child\n",
        "            for child in node.children:\n",
        "                self._pre_order_traversal(child)\n",
        "    def post_order_traversal(self):\n",
        "        if self.root:\n",
        "            self._post_order_traversal(self.root)\n",
        "\n",
        "    def _post_order_traversal(self, node):\n",
        "        if node:\n",
        "            # Recursively traverse each child\n",
        "            for child in node.children:\n",
        "                self._post_order_traversal(child)\n",
        "\n",
        "            # Visit the keys\n",
        "            print(node.keys, end=\" \")\n",
        "    def in_order_traversal(self):\n",
        "        if self.root:\n",
        "            self._in_order_traversal(self.root)\n",
        "\n",
        "    def _in_order_traversal(self, node):\n",
        "        if node:\n",
        "            # Traverse each child and its associated key\n",
        "            for i in range(len(node.keys)):\n",
        "                # Recursively traverse the left child\n",
        "                if i < len(node.children):\n",
        "                  self._in_order_traversal(node.children[i])\n",
        "\n",
        "                # Print the key\n",
        "                print(node.keys[i], end=\" \")\n",
        "\n",
        "            # Traverse the rightmost child\n",
        "            if len(node.children) > len(node.keys):\n",
        "              self._in_order_traversal(node.children[-1])\n",
        "\n",
        "    def bfs(self):\n",
        "      if self.root:\n",
        "            self._bfs(self.root)\n",
        "    def _bfs(self,node):\n",
        "        if not self.root:\n",
        "            return\n",
        "        # Use a queue for level-order traversal\n",
        "        queue = deque([self.root])\n",
        "        while queue:\n",
        "            current_level_size = len(queue)\n",
        "\n",
        "            for _ in range(current_level_size):\n",
        "                node = queue.popleft()\n",
        "\n",
        "                # Print keys in the current node\n",
        "                print(node.keys, end=\" \")\n",
        "\n",
        "                # Enqueue child nodes if they exist\n",
        "                if not node.leaf:\n",
        "                    queue.extend(node.children)\n",
        "\n",
        "    def print_by_levels(self):\n",
        "        if not self.root:\n",
        "            print(\"B-tree is empty\")\n",
        "            return\n",
        "\n",
        "        # Use a queue for level-order traversal\n",
        "        queue = deque([self.root])\n",
        "\n",
        "        while queue:\n",
        "            current_level_size = len(queue)\n",
        "\n",
        "            for _ in range(current_level_size):\n",
        "                node = queue.popleft()\n",
        "\n",
        "                # Print keys in the current node\n",
        "                print(node.keys, end=\" \")\n",
        "\n",
        "                # Enqueue child nodes if they exist\n",
        "                if not node.leaf:\n",
        "                    queue.extend(node.children)\n",
        "\n",
        "            print()  # Move to the next line for the next level\n"
      ],
      "metadata": {
        "id": "r7MjfgSySA77"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Data File Parsing\n",
        "### Please Upload the file address in this part of the code : )\n",
        "Example: file(\"Address_to_the_file\")"
      ],
      "metadata": {
        "id": "fczhKfLgWSqh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#make sure to write the exact file destination address to this function to run.\n",
        "def file(file_name):\n",
        "  import pandas as pd\n",
        "  import csv\n",
        "  #fining the file format based on the last 3 characters after the period and based on the file format writing a read function\n",
        "  file_name_split = file_name.split('.')[-1].lower()\n",
        "  if file_name_split == 'csv':\n",
        "      df=pd.read_csv(file_name)\n",
        "  elif file_name_split ==' xlsx':\n",
        "      df=pd.read_excel(file_name)\n",
        "  else:\n",
        "      return 'Unknown File Format'\n",
        "  # df=pd.read_csv(file_name)\n",
        "  # Create a DataFrame using the extracted data and prinitng the first 2 rows for reference\n",
        "  df = pd.DataFrame(df)\n",
        "  print(\"here is a the sample DF for reference\")\n",
        "  print(df.head(2))\n",
        "  #since the id's are usually present in the first column making it default to zero without bothering the user with more questions :)\n",
        "  #index_ask=int(input(\"Enter the index(startting with 0) of the column with the ID's or nodes: \"))\n",
        "  index_ask=0\n",
        "  #asking for min degree\n",
        "  min_degree=int(input(\"What's the min degree (t) you would like to be (2/3/4/5)?: \"))\n",
        "  btree=BTree(min_degree)\n",
        "  #iteratively looping through the first column of the index and inserting the elements to the btree\n",
        "  for x in df.iloc[0:,index_ask]:\n",
        "    #print(x, \"-> inserted\")\n",
        "    btree.insert(x)\n",
        "  status=True\n",
        "  #priniting the tree by levels\n",
        "  btree.print_by_levels()\n",
        "  #asking user for that operation would they like to do\n",
        "  '''\n",
        "  1. Search\n",
        "  2. Remove\n",
        "  3. Traversals\n",
        "    a. DFS\n",
        "      i. Pre Order\n",
        "      ii. In Order\n",
        "      iii. Post Order\n",
        "    b. BFS (Level Order)\n",
        "  4. Exit\n",
        "  '''\n",
        "  while status==True:\n",
        "    user_input=input(\"Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): \")\n",
        "    user_input.lower()\n",
        "    if user_input==\"t\" or user_input==\"traversals\" or user_input==\"traversal\":\n",
        "      user_input2=str(input(\"Preorder(1)/InOrder(2)/PostOrder(3)/Level Order(BFS)(4): \"))\n",
        "      if user_input2=='1':\n",
        "        print(\"Root-Left Subtree- Right Subtree\")\n",
        "        btree.pre_order_traversal()\n",
        "      if user_input2=='2':\n",
        "        print(\"Left Subtree -Root- Right Subtree\")\n",
        "        btree.in_order_traversal()\n",
        "      if user_input2=='3':\n",
        "        print(\"Left Subtree - Right Subtree- Root\")\n",
        "        print(btree.post_order_traversal())\n",
        "      if user_input2=='4' or user_input2==\"bfs\" or user_input2==\"BFS\":\n",
        "        print(\"Level Order Traversal\")\n",
        "        print(btree.bfs())\n",
        "    if user_input ==\"s\" or user_input==\"search\":\n",
        "      s_element=int(input(\"What element would you like to search for?: \"))\n",
        "      s_bool=btree.search(s_element)\n",
        "      print(s_bool)\n",
        "      if s_bool== True:\n",
        "        #print(df.iloc[s_element,:])\n",
        "        filtered_df = df[df[df.columns[index_ask]] == s_element]\n",
        "        print(filtered_df)\n",
        "      else:\n",
        "        pass\n",
        "    if user_input==\"r\" or user_input==\"remove\":\n",
        "      r_element=int(input(\"What element would you like to remove?: \"))\n",
        "      btree.delete(r_element)\n",
        "      r_df=df[df[df.columns[index_ask]] == r_element]\n",
        "      df = df[~df[df.columns[index_ask]].isin(r_df[df.columns[index_ask]])]\n",
        "      print(\"The Updated Tree is: \")\n",
        "      btree.print_by_levels()\n",
        "      #print(df)\n",
        "    if user_input==\"e\" or user_input==\"exit\":\n",
        "      print(\"Here is the Final BTree\")\n",
        "      btree.print_by_levels()\n",
        "      status=False\n",
        "\n",
        "# write the address to the exact datafile\n",
        "file(\"Iris.csv\")\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aLXJKA2OWSYC",
        "outputId": "56b2fe49-d7cc-4d40-d17b-7467b9d81897"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "here is a the sample DF for reference\n",
            "   Id  SepalLengthCm  SepalWidthCm  PetalLengthCm  PetalWidthCm      Species\n",
            "0   1            5.1           3.5            1.4           0.2  Iris-setosa\n",
            "1   2            4.9           3.0            1.4           0.2  Iris-setosa\n",
            "What's the min degree (t) you would like to be (2/3/4/5)?: 3\n",
            "[27, 54, 81, 108] \n",
            "[9, 18] [36, 45] [63, 72] [90, 99] [117, 126, 135] \n",
            "[3, 6] [12, 15] [21, 24] [30, 33] [39, 42] [48, 51] [57, 60] [66, 69] [75, 78] [84, 87] [93, 96] [102, 105] [111, 114] [120, 123] [129, 132] [138, 141, 144, 147] \n",
            "[1, 2] [4, 5] [7, 8] [10, 11] [13, 14] [16, 17] [19, 20] [22, 23] [25, 26] [28, 29] [31, 32] [34, 35] [37, 38] [40, 41] [43, 44] [46, 47] [49, 50] [52, 53] [55, 56] [58, 59] [61, 62] [64, 65] [67, 68] [70, 71] [73, 74] [76, 77] [79, 80] [82, 83] [85, 86] [88, 89] [91, 92] [94, 95] [97, 98] [100, 101] [103, 104] [106, 107] [109, 110] [112, 113] [115, 116] [118, 119] [121, 122] [124, 125] [127, 128] [130, 131] [133, 134] [136, 137] [139, 140] [142, 143] [145, 146] [148, 149, 150] \n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): s\n",
            "What element would you like to search for?: 24\n",
            "True\n",
            "    Id  SepalLengthCm  SepalWidthCm  PetalLengthCm  PetalWidthCm      Species\n",
            "23  24            5.1           3.3            1.7           0.5  Iris-setosa\n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): s\n",
            "What element would you like to search for?: 45\n",
            "True\n",
            "    Id  SepalLengthCm  SepalWidthCm  PetalLengthCm  PetalWidthCm      Species\n",
            "44  45            5.1           3.8            1.9           0.4  Iris-setosa\n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): r\n",
            "What element would you like to remove?: 45\n",
            "The Updated Tree is: \n",
            "[27, 54, 81, 108] \n",
            "[9, 18] [36, 44] [63, 72] [90, 99] [117, 126, 135] \n",
            "[3, 6] [12, 15] [21, 24] [30, 33] [39, 42] [48, 51] [57, 60] [66, 69] [75, 78] [84, 87] [93, 96] [102, 105] [111, 114] [120, 123] [129, 132] [138, 141, 144, 147] \n",
            "[1, 2] [4, 5] [7, 8] [10, 11] [13, 14] [16, 17] [19, 20] [22, 23] [25, 26] [28, 29] [31, 32] [34, 35] [37, 38] [40, 41] [43] [46, 47] [49, 50] [52, 53] [55, 56] [58, 59] [61, 62] [64, 65] [67, 68] [70, 71] [73, 74] [76, 77] [79, 80] [82, 83] [85, 86] [88, 89] [91, 92] [94, 95] [97, 98] [100, 101] [103, 104] [106, 107] [109, 110] [112, 113] [115, 116] [118, 119] [121, 122] [124, 125] [127, 128] [130, 131] [133, 134] [136, 137] [139, 140] [142, 143] [145, 146] [148, 149, 150] \n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): s\n",
            "What element would you like to search for?: 45\n",
            "False\n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): r\n",
            "What element would you like to remove?: 81\n",
            "The Updated Tree is: \n",
            "[27, 54, 80, 108] \n",
            "[9, 18] [36, 44] [63, 72] [90, 99] [117, 126, 135] \n",
            "[3, 6] [12, 15] [21, 24] [30, 33] [39, 42] [48, 51] [57, 60] [66, 69] [75, 78] [84, 87] [93, 96] [102, 105] [111, 114] [120, 123] [129, 132] [138, 141, 144, 147] \n",
            "[1, 2] [4, 5] [7, 8] [10, 11] [13, 14] [16, 17] [19, 20] [22, 23] [25, 26] [28, 29] [31, 32] [34, 35] [37, 38] [40, 41] [43] [46, 47] [49, 50] [52, 53] [55, 56] [58, 59] [61, 62] [64, 65] [67, 68] [70, 71] [73, 74] [76, 77] [79] [82, 83] [85, 86] [88, 89] [91, 92] [94, 95] [97, 98] [100, 101] [103, 104] [106, 107] [109, 110] [112, 113] [115, 116] [118, 119] [121, 122] [124, 125] [127, 128] [130, 131] [133, 134] [136, 137] [139, 140] [142, 143] [145, 146] [148, 149, 150] \n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): s\n",
            "What element would you like to search for?: 81\n",
            "False\n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): t\n",
            "Preorder(1)/InOrder(2)/PostOrder(3)/Level Order(BFS)(4): 1\n",
            "Root-Left Subtree- Right Subtree\n",
            "[27, 54, 80, 108] [9, 18] [3, 6] [1, 2] [4, 5] [7, 8] [12, 15] [10, 11] [13, 14] [16, 17] [21, 24] [19, 20] [22, 23] [25, 26] [36, 44] [30, 33] [28, 29] [31, 32] [34, 35] [39, 42] [37, 38] [40, 41] [43] [48, 51] [46, 47] [49, 50] [52, 53] [63, 72] [57, 60] [55, 56] [58, 59] [61, 62] [66, 69] [64, 65] [67, 68] [70, 71] [75, 78] [73, 74] [76, 77] [79] [90, 99] [84, 87] [82, 83] [85, 86] [88, 89] [93, 96] [91, 92] [94, 95] [97, 98] [102, 105] [100, 101] [103, 104] [106, 107] [117, 126, 135] [111, 114] [109, 110] [112, 113] [115, 116] [120, 123] [118, 119] [121, 122] [124, 125] [129, 132] [127, 128] [130, 131] [133, 134] [138, 141, 144, 147] [136, 137] [139, 140] [142, 143] [145, 146] [148, 149, 150] Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): t\n",
            "Preorder(1)/InOrder(2)/PostOrder(3)/Level Order(BFS)(4): 2\n",
            "Left Subtree -Root- Right Subtree\n",
            "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): t\n",
            "Preorder(1)/InOrder(2)/PostOrder(3)/Level Order(BFS)(4): 3\n",
            "Left Subtree - Right Subtree- Root\n",
            "[1, 2] [4, 5] [7, 8] [3, 6] [10, 11] [13, 14] [16, 17] [12, 15] [19, 20] [22, 23] [25, 26] [21, 24] [9, 18] [28, 29] [31, 32] [34, 35] [30, 33] [37, 38] [40, 41] [43] [39, 42] [46, 47] [49, 50] [52, 53] [48, 51] [36, 44] [55, 56] [58, 59] [61, 62] [57, 60] [64, 65] [67, 68] [70, 71] [66, 69] [73, 74] [76, 77] [79] [75, 78] [63, 72] [82, 83] [85, 86] [88, 89] [84, 87] [91, 92] [94, 95] [97, 98] [93, 96] [100, 101] [103, 104] [106, 107] [102, 105] [90, 99] [109, 110] [112, 113] [115, 116] [111, 114] [118, 119] [121, 122] [124, 125] [120, 123] [127, 128] [130, 131] [133, 134] [129, 132] [136, 137] [139, 140] [142, 143] [145, 146] [148, 149, 150] [138, 141, 144, 147] [117, 126, 135] [27, 54, 80, 108] None\n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): t\n",
            "Preorder(1)/InOrder(2)/PostOrder(3)/Level Order(BFS)(4): 4\n",
            "Level Order Traversal\n",
            "[27, 54, 80, 108] [9, 18] [36, 44] [63, 72] [90, 99] [117, 126, 135] [3, 6] [12, 15] [21, 24] [30, 33] [39, 42] [48, 51] [57, 60] [66, 69] [75, 78] [84, 87] [93, 96] [102, 105] [111, 114] [120, 123] [129, 132] [138, 141, 144, 147] [1, 2] [4, 5] [7, 8] [10, 11] [13, 14] [16, 17] [19, 20] [22, 23] [25, 26] [28, 29] [31, 32] [34, 35] [37, 38] [40, 41] [43] [46, 47] [49, 50] [52, 53] [55, 56] [58, 59] [61, 62] [64, 65] [67, 68] [70, 71] [73, 74] [76, 77] [79] [82, 83] [85, 86] [88, 89] [91, 92] [94, 95] [97, 98] [100, 101] [103, 104] [106, 107] [109, 110] [112, 113] [115, 116] [118, 119] [121, 122] [124, 125] [127, 128] [130, 131] [133, 134] [136, 137] [139, 140] [142, 143] [145, 146] [148, 149, 150] None\n",
            "Would you like to search(s)/remove(r)/DFS, BFS traversals(t)/exit(e): e\n",
            "Here is the Final BTree\n",
            "[27, 54, 80, 108] \n",
            "[9, 18] [36, 44] [63, 72] [90, 99] [117, 126, 135] \n",
            "[3, 6] [12, 15] [21, 24] [30, 33] [39, 42] [48, 51] [57, 60] [66, 69] [75, 78] [84, 87] [93, 96] [102, 105] [111, 114] [120, 123] [129, 132] [138, 141, 144, 147] \n",
            "[1, 2] [4, 5] [7, 8] [10, 11] [13, 14] [16, 17] [19, 20] [22, 23] [25, 26] [28, 29] [31, 32] [34, 35] [37, 38] [40, 41] [43] [46, 47] [49, 50] [52, 53] [55, 56] [58, 59] [61, 62] [64, 65] [67, 68] [70, 71] [73, 74] [76, 77] [79] [82, 83] [85, 86] [88, 89] [91, 92] [94, 95] [97, 98] [100, 101] [103, 104] [106, 107] [109, 110] [112, 113] [115, 116] [118, 119] [121, 122] [124, 125] [127, 128] [130, 131] [133, 134] [136, 137] [139, 140] [142, 143] [145, 146] [148, 149, 150] \n"
          ]
        }
      ]
    }
  ]
}