day-4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Insertion in a BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinarySearchTree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "\n",
    "    \n",
    "    def insert(self, data):\n",
    "        if self.root is None:\n",
    "            self.root = Node(data)\n",
    "        else:\n",
    "            self._insert_recursive(self.root, data)\n",
    "    \n",
    "    def _insert_recursive(self, node, data):\n",
    "        if data < node.data:\n",
    "            if node.left is None:\n",
    "                node.left = Node(data)\n",
    "            else:\n",
    "                self._insert_recursive(node.left, data)\n",
    "        else:\n",
    "            if node.right is None:\n",
    "                node.right = Node(data)\n",
    "            else:\n",
    "                self._insert_recursive(node.right, data)\n",
    "\n",
    "    def search(self, key):\n",
    "        return self._search_recursive(self.root, key)\n",
    "\n",
    "    def _search_recursive(self, node, key):\n",
    "        if node is None or node.data == key:\n",
    "            return node\n",
    "\n",
    "        if key < node.data:\n",
    "            return self._search_recursive(node.left, key)\n",
    "        \n",
    "        return self._search_recursive(node.right, key)\n",
    "    \n",
    "\n",
    "    def delete_BST(self, key):\n",
    "        self.root = self._delete_recursive(self.root, key)\n",
    "\n",
    "    def _delete_recursive(self, node, key):\n",
    "        if node is None:\n",
    "            return node\n",
    "        \n",
    "        if key < node.data:\n",
    "            node.left = self._delete_recursive(node.left, key)\n",
    "        elif key > node.data:\n",
    "            node.right = self._delete_recursive(node.right, key)\n",
    "        else:\n",
    "            if node.left is None:\n",
    "                return node.right\n",
    "            elif node.right is None:\n",
    "                return node.left\n",
    "            \n",
    "            temp = self._min_value_node(node.right)\n",
    "            node.data = temp.data\n",
    "            node.right = self._delete_recursive(node.right, temp.data)\n",
    "\n",
    "        return node\n",
    "    \n",
    "    def _min_value_node(self, node):\n",
    "        current = node\n",
    "        while current.left is not None:\n",
    "            current = current.left\n",
    "        \n",
    "        return current\n",
    "    \n",
    "    def inorder_traversal(self, node):\n",
    "        if node:\n",
    "            self.inorder_traversal(node.left)\n",
    "            print(node.data, end=\" \")\n",
    "            self.inorder_traversal(node.right)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node with key: 20\n",
      "Node not found\n",
      "20 30 50 60 70 80 "
     ]
    }
   ],
   "source": [
    "bst = BinarySearchTree()\n",
    "bst.insert(50)\n",
    "bst.insert(30)\n",
    "bst.insert(70)\n",
    "bst.insert(20)\n",
    "bst.insert(40)\n",
    "bst.insert(60)\n",
    "bst.insert(80)\n",
    "\n",
    "\n",
    "node = bst.search(20)\n",
    "if node:\n",
    "    print(f\"Node with key: {node.data}\")\n",
    "else:\n",
    "    print(\"Node not found\")\n",
    "\n",
    "bst.delete_BST(40)\n",
    "\n",
    "\n",
    "node1 = bst.search(40)\n",
    "if node1:\n",
    "    print(f\"Node with key: {node1.data}\")\n",
    "else:\n",
    "    print(\"Node not found\")\n",
    "\n",
    "bst.inorder_traversal(bst.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorting Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Bubble Sort:\n",
    "+ In bubble sort, we repeatedly compare adjacent elements and swap them if they are in the wrong order. This process is repeated for every element in the list until the list is sorted.\n",
    "\n",
    "##### Time complexity:\n",
    "+ Worst-case: O(n^2)\n",
    "+ Best-case (when array is already sorted): O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original array:  [64, 34, 25, 12, 22, 11, 90]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Processing....:  71%|███████▏  | 5/7 [00:00<00:00, 54613.33it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array:  [11, 12, 22, 25, 34, 64, 90]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "from tqdm import tqdm\n",
    "\n",
    "def bubble_sort(arr):\n",
    "    n = len(arr)\n",
    "    barh = tqdm(total=n, desc=\"Processing....\")  \n",
    "\n",
    "    for i in range(n):\n",
    "        swapped = False\n",
    "\n",
    "        for j in range(0, n - i - 1):\n",
    "            if arr[j] > arr[j + 1]:\n",
    "                arr[j], arr[j + 1] = arr[j + 1], arr[j]\n",
    "                swapped = True\n",
    "\n",
    "        if not swapped:\n",
    "            break\n",
    "\n",
    "        barh.update(1) \n",
    "\n",
    "    barh.close()\n",
    "\n",
    "\n",
    "arr = [64, 34, 25, 12, 22, 11, 90]\n",
    "# arr = [1,2,3,4,5]\n",
    "\n",
    "print(\"Original array: \", arr)\n",
    "bubble_sort(arr)\n",
    "print(\"Sorted array: \", arr)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. Selection Sort\n",
    "+ Selection sort divides the array into two parts: Sorted and unsorted.\n",
    "+ In each iteration, it selects the minimum element from unsorted part and swaps it with the first unsorted element.\n",
    "\n",
    "##### Time complexity:\n",
    " + O(n^2) for all cases (since it always goes though the whole list to find the minimum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Processing....: 100%|██████████| 5/5 [00:00<00:00, 58416.49it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array using Selection Sort: [11, 12, 22, 25, 64]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "def selection_sort(arr):\n",
    "    n = len(arr)\n",
    "    barh = tqdm(total=n, desc=f\"Processing....\")\n",
    "\n",
    "    for i in range(n):\n",
    "        min_index = i  # assume the first element is the minimum\n",
    "\n",
    "        \n",
    "        for j in range(i + 1, n):\n",
    "            if arr[j] < arr[min_index]:\n",
    "                min_index = j\n",
    "            \n",
    "        # swap the found minimum with the first unsorted element\n",
    "        arr[i], arr[min_index] = arr[min_index], arr[i]\n",
    "\n",
    "        barh.update(1)\n",
    "    \n",
    "    barh.close()\n",
    "\n",
    "\n",
    "arr = [64, 25, 12, 22, 11]\n",
    "selection_sort(arr)\n",
    "print(\"Sorted array using Selection Sort:\", arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3. Insertion Sort\n",
    "+ Insertion sort works similarly to sorting playing cards in your hands.\n",
    "+ It picks one element from the unsorted part and inserts it in the correct position in the sorted part.\n",
    "\n",
    "##### Time complexity:\n",
    "+ Worst-case: O(n^2)\n",
    "+ Best-case (nearly sorted): O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Processing....:  80%|████████  | 4/5 [00:00<00:00, 37957.50it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array using Insertion Sort: [5, 6, 11, 12, 13]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "def insertion_sort(arr):\n",
    "    n = len(arr)\n",
    "\n",
    "    barh = tqdm(total=n, desc=\"Processing....\")\n",
    "\n",
    "    for i in range(1, n):\n",
    "        key = arr[i]\n",
    "        j = i - 1\n",
    "\n",
    "        while j >= 0 and key < arr[j]:\n",
    "            arr[j + 1] = arr[j]\n",
    "            j -= 1\n",
    "\n",
    "        arr[j + 1] = key\n",
    "\n",
    "        barh.update(1)\n",
    "\n",
    "    barh.close()\n",
    "    \n",
    "\n",
    "\n",
    "arr = [12, 11, 13, 5, 6]\n",
    "insertion_sort(arr)\n",
    "print(\"Sorted array using Insertion Sort:\", arr)"
   ]
  }
 ],
 "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.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}