03_Data Structures/ds COMPLETE.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "385232ec",
   "metadata": {},
   "source": [
    "# Data Structures\n",
    "\n",
    "- Linked List (Linear)\n",
    "- Stack\n",
    "- Queue (Linear, Circular)\n",
    "- Binary Search Tree (Normal, Freespace)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2bfb6ce0",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47580729",
   "metadata": {},
   "source": [
    "## Linked List\n",
    "A linked list is a linear data structure composed of a series of connected nodes. In a singly-linked list, each node contains data and a reference (or link) to the next node in the list. The first node is called the head, and the last node's reference is set to `None`.\n",
    "\n",
    "### Main Methods\n",
    "- **insert / delete**: The `insert` operation inserts a new node at the end of the list, while `delete` deletes a node.\n",
    "- **sort_it**: Sorts the linked list based on the values stored in the nodes.\n",
    "- **find**: Searches for a particular value or node within the linked list.\n",
    "\n",
    "### Side Methods\n",
    "- **empty**: Checks whether the linked list is empty by verifying if the head node is `None`.\n",
    "- **size**: Returns the number of nodes in the linked list.\n",
    "- **display**: Displays the contents of the linked list by traversing through each node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a53ca6d1",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "test: [91, 64, 96, 52, 14, 94, 85, 70, 47, 72, 43, 51, 99, 17, 93]\n",
      "notinlst: [91, 64, 96, 52, 14]\n",
      "inlst: [94, 85, 70, 47, 72, 43, 51]\n",
      "after_empty: [99, 17, 93]\n",
      "\n",
      ">>> LLL:\n",
      "Size: 6 | Data (  ):       |        | LLL: [43, 47, 51, 70, 72, 85, 94] | True\n",
      "\n",
      "Not In List:\n",
      "Size: 6 | Data (91): False | Done | LLL: [43, 47, 51, 70, 72, 85, 94]\n",
      "Size: 6 | Data (64): False | Done | LLL: [43, 47, 51, 70, 72, 85, 94]\n",
      "Size: 6 | Data (96): False | Done | LLL: [43, 47, 51, 70, 72, 85, 94]\n",
      "Size: 6 | Data (52): False | Done | LLL: [43, 47, 51, 70, 72, 85, 94]\n",
      "Size: 6 | Data (14): False | Done | LLL: [43, 47, 51, 70, 72, 85, 94]\n",
      "\n",
      "In List:\n",
      "Size: 6 | Data (94): True | Done | LLL: [43, 47, 51, 70, 72, 85]\n",
      "Size: 5 | Data (85): True | Done | LLL: [43, 47, 51, 70, 72]\n",
      "Size: 4 | Data (70): True | Done | LLL: [43, 47, 51, 72]\n",
      "Size: 3 | Data (47): True | Done | LLL: [43, 51, 72]\n",
      "Size: 2 | Data (72): True | Done | LLL: [43, 51]\n",
      "Size: 1 | Data (43): True | Done | LLL: [51]\n",
      "Size: 0 | Data (51): True | Done | LLL: []\n",
      "\n",
      "Empty:\n",
      "Size: -1 | Data (99): False | Done | LLL: []\n",
      "Size: -1 | Data (17): False | Done | LLL: []\n",
      "Size: -1 | Data (93): False | Done | LLL: []\n"
     ]
    }
   ],
   "source": [
    "# Linear Linked List\n",
    "class Node:\n",
    "    def __init__(self, data, next_ptr=None):\n",
    "        self.data = data\n",
    "        self.next_ptr = next_ptr\n",
    "        \n",
    "    def get_data(self):\n",
    "        return self.data\n",
    "    \n",
    "    def set_data(self, data):\n",
    "        self.data = data\n",
    "        \n",
    "    def get_next(self):\n",
    "        return self.next_ptr\n",
    "    \n",
    "    def set_next(self, next_node):\n",
    "        self.next_ptr = next_node\n",
    "        \n",
    "class LinearLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.size = 0\n",
    "        \n",
    "    def empty(self):\n",
    "        return self.head is None\n",
    "    \n",
    "    def insert(self, data):  \n",
    "        ## Put the new data in the head of the linkedlist\n",
    "        \n",
    "        # Empty: Update the head and tail\n",
    "        if self.empty():\n",
    "            self.head = Node(data)\n",
    "        else:\n",
    "            self.head = Node(data, self.head)\n",
    "            self.size += 1\n",
    "\n",
    "            \n",
    "    def sort_it(self):  \n",
    "        if self.empty():  \n",
    "            return\n",
    "        \n",
    "        # Bubble sort\n",
    "        curr_node = self.head\n",
    "        while curr_node:    \n",
    "            next_node = curr_node.get_next()\n",
    "            while next_node:\n",
    "                if curr_node.get_data() > next_node.get_data():\n",
    "                    temp = next_node.get_data()\n",
    "                    next_node.set_data(curr_node.get_data())\n",
    "                    curr_node.set_data(temp)\n",
    "                next_node = next_node.get_next()\n",
    "            curr_node = curr_node.get_next()\n",
    "            \n",
    "    def delete(self, target):\n",
    "        def helper(curr_node):\n",
    "            if curr_node:\n",
    "                if curr_node.get_data() == target:\n",
    "                    self.size -= 1\n",
    "                    return curr_node.get_next()\n",
    "                \n",
    "                curr_node.set_next(helper(curr_node.get_next()))\n",
    "                return curr_node\n",
    "        \n",
    "        self.head = helper(self.head)\n",
    "        return \"Done\"\n",
    "    \n",
    "    def search(self, target):\n",
    "        curr_node = self.head\n",
    "        while curr_node:\n",
    "            if curr_node.get_data() == target:\n",
    "                return True\n",
    "            curr_node = curr_node.get_next()\n",
    "        return False\n",
    "\n",
    "    def size_of(self):\n",
    "        return self.size\n",
    "    \n",
    "    def display(self):\n",
    "        nodes = []\n",
    "        curr_node = self.head\n",
    "        # Loop through all filled nodes\n",
    "        while curr_node:\n",
    "            nodes.append(curr_node.get_data())\n",
    "            curr_node = curr_node.get_next()\n",
    "        return nodes\n",
    "    \n",
    "# Test\n",
    "from ds_backup.ds_tests import LLL_Test\n",
    "LLL_Test(LinearLinkedList)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8ed0298",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddc90c09",
   "metadata": {},
   "source": [
    "## Sorted variation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c6cd2711",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "test: [33, 25, 15, 99, 36, 20, 11, 93, 81, 91, 72, 23, 38, 56, 83, 78, 29, 65]\n",
      "notinlst: [33, 25, 15, 99, 36, 20]\n",
      "inlst: [11, 93, 81, 91, 72, 23, 38, 56, 83]\n",
      "after_empty: [78, 29, 65]\n",
      "\n",
      ">>> LLL:\n",
      "Size: 9 | Data (  ):       |        | LLL: [11, 23, 38, 56, 72, 81, 83, 91, 93] | True\n",
      "\n",
      "Not In List:\n",
      "Size: 9 | Data (33): False | Done | LLL: [11, 23, 38, 56, 72, 81, 83, 91, 93]\n",
      "Size: 9 | Data (25): False | Done | LLL: [11, 23, 38, 56, 72, 81, 83, 91, 93]\n",
      "Size: 9 | Data (15): False | Done | LLL: [11, 23, 38, 56, 72, 81, 83, 91, 93]\n",
      "Size: 9 | Data (99): False | Done | LLL: [11, 23, 38, 56, 72, 81, 83, 91, 93]\n",
      "Size: 9 | Data (36): False | Done | LLL: [11, 23, 38, 56, 72, 81, 83, 91, 93]\n",
      "Size: 9 | Data (20): False | Done | LLL: [11, 23, 38, 56, 72, 81, 83, 91, 93]\n",
      "\n",
      "In List:\n",
      "Size: 9 | Data (11): True | Done | LLL: [23, 38, 56, 72, 81, 83, 91, 93]\n",
      "Size: 8 | Data (93): True | Done | LLL: [23, 38, 56, 72, 81, 83, 91]\n",
      "Size: 7 | Data (81): True | Done | LLL: [23, 38, 56, 72, 83, 91]\n",
      "Size: 6 | Data (91): True | Done | LLL: [23, 38, 56, 72, 83]\n",
      "Size: 5 | Data (72): True | Done | LLL: [23, 38, 56, 83]\n",
      "Size: 4 | Data (23): True | Done | LLL: [38, 56, 83]\n",
      "Size: 3 | Data (38): True | Done | LLL: [56, 83]\n",
      "Size: 2 | Data (56): True | Done | LLL: [83]\n",
      "Size: 1 | Data (83): True | Done | LLL: []\n",
      "\n",
      "Empty:\n",
      "Size: 0 | Data (78): False | Done | LLL: []\n",
      "Size: 0 | Data (29): False | Done | LLL: []\n",
      "Size: 0 | Data (65): False | Done | LLL: []\n"
     ]
    }
   ],
   "source": [
    "class SortedLinkedList(LinearLinkedList):\n",
    "    def __init__(self):\n",
    "        super().__init__()\n",
    "        \n",
    "    def insert(self, data):\n",
    "        def helper(curr_node, new_node):\n",
    "            if curr_node is None:\n",
    "                return new_node\n",
    "            \n",
    "            if curr_node.get_data() > new_node.get_data():\n",
    "                new_node.set_next(curr_node)\n",
    "                return new_node\n",
    "            \n",
    "            curr_node.set_next(helper(curr_node.get_next(), new_node))\n",
    "            return curr_node\n",
    "        \n",
    "        new_node = Node(data)\n",
    "        if not self.empty():\n",
    "            self.head = helper(self.head, new_node)\n",
    "        else:\n",
    "            self.head = new_node\n",
    "        self.size += 1\n",
    "    \n",
    "# Test\n",
    "from ds_backup.ds_tests import LLL_Test\n",
    "LLL_Test(SortedLinkedList)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1613ba0d",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7863a4b2",
   "metadata": {},
   "source": [
    "## Stack\n",
    "A stack is a linear data structure that follows the First-In-Last-Out (FILO) principle, meaning that the last element added is the first one to be removed.\n",
    "\n",
    "### Main Methods\n",
    "- **push / pop**: These methods are used to add an element to the top of the stack (push) or remove the topmost element from the stack (pop).\n",
    "- **peek**: This method allows you to examine the topmost element of the stack without removing it.\n",
    "\n",
    "### Side Methods\n",
    "- **valid**: This method checks if the stack is empty by verifying if there are any elements in it.\n",
    "- **size**: This method returns the number of elements currently in the stack.\n",
    "- **display**: This method displays the elements of the stack in the order they would be popped, starting from the top.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1a0af7bb",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List: [40, 33, 68, 24, 78, 61, 22, 71, 46, 80]\n",
      "\n",
      ">>> Stack:\n",
      "Stack: [] | Size: 0 | Top: Empty!\n",
      "\n",
      "Top: 80 | Stack: [40, 33, 68, 24, 78, 61, 22, 71, 46, 80]\n",
      "\n",
      "Popped: 80 | Top: 46 | Size: 9 | Stack: [40, 33, 68, 24, 78, 61, 22, 71, 46]\n",
      "Popped: 46 | Top: 71 | Size: 8 | Stack: [40, 33, 68, 24, 78, 61, 22, 71]\n",
      "Popped: 71 | Top: 22 | Size: 7 | Stack: [40, 33, 68, 24, 78, 61, 22]\n",
      "Popped: 22 | Top: 61 | Size: 6 | Stack: [40, 33, 68, 24, 78, 61]\n",
      "Popped: 61 | Top: 78 | Size: 5 | Stack: [40, 33, 68, 24, 78]\n",
      "Popped: 78 | Top: 24 | Size: 4 | Stack: [40, 33, 68, 24]\n",
      "Popped: 24 | Top: 68 | Size: 3 | Stack: [40, 33, 68]\n",
      "Popped: 68 | Top: 33 | Size: 2 | Stack: [40, 33]\n",
      "Popped: 33 | Top: 40 | Size: 1 | Stack: [40]\n",
      "Popped: 40 | Top: Empty! | Size: 0 | Stack: []\n"
     ]
    }
   ],
   "source": [
    "## Stack\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self._stack = []\n",
    "        \n",
    "    def push(self, data): # Insert new data\n",
    "        self._stack.append(data)\n",
    "    \n",
    "    def pop(self): # Remove latest data\n",
    "        if self._stack:\n",
    "            return self._stack.pop()\n",
    "        return \"Empty!\"\n",
    "    \n",
    "    def peek(self): # See latest data\n",
    "        if self._stack:\n",
    "            return self._stack[-1]\n",
    "        return \"Empty!\"\n",
    "    \n",
    "    def size(self): # find size\n",
    "        return len(self._stack)\n",
    "    \n",
    "    def display(self):\n",
    "        return self._stack\n",
    "\n",
    "# Test\n",
    "from ds_backup.ds_tests import Stack_Test\n",
    "Stack_Test(Stack)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35055566",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d0854665",
   "metadata": {},
   "source": [
    "## Queue\n",
    "> First In - First Out (FIFO)\n",
    "\n",
    "## Linear\n",
    "### Main Methods\n",
    "- **enqueue / dequeue**: `enqueue` adds an element to the rear of the queue, `dequeue` removes an element from the front of the queue\n",
    "- **peek**: Examine the element at the front of the queue without removing it.\n",
    "\n",
    "### Side Methods\n",
    "- **valid**: Checks if the queue is empty by verifying if there are any elements in it.\n",
    "- **size**: Returns the number of elements currently in the queue.\n",
    "- **display**: Displays the elements of the queue in the order they would be dequeued, starting from the front.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c11d5070",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List: [49, 99, 96, 54, 89, 68, 22, 58, 62, 91]\n",
      ">>> LQ:\n",
      "LQ: [] | Size: 0 | Front: Empty!\n",
      "\n",
      "Front: 49 | LQ: [49, 99, 96, 54, 89, 68, 22, 58, 62, 91]\n",
      "\n",
      "Deq: 49 | Front: 99 | Size: 9 | LQ: [99, 96, 54, 89, 68, 22, 58, 62, 91]\n",
      "Deq: 99 | Front: 96 | Size: 8 | LQ: [96, 54, 89, 68, 22, 58, 62, 91]\n",
      "Deq: 96 | Front: 54 | Size: 7 | LQ: [54, 89, 68, 22, 58, 62, 91]\n",
      "Deq: 54 | Front: 89 | Size: 6 | LQ: [89, 68, 22, 58, 62, 91]\n",
      "Deq: 89 | Front: 68 | Size: 5 | LQ: [68, 22, 58, 62, 91]\n",
      "Deq: 68 | Front: 22 | Size: 4 | LQ: [22, 58, 62, 91]\n",
      "Deq: 22 | Front: 58 | Size: 3 | LQ: [58, 62, 91]\n",
      "Deq: 58 | Front: 62 | Size: 2 | LQ: [62, 91]\n",
      "Deq: 62 | Front: 91 | Size: 1 | LQ: [91]\n",
      "Deq: 91 | Front: Empty! | Size: 0 | LQ: []\n"
     ]
    }
   ],
   "source": [
    "# Linear Queue\n",
    "class LinearQueue:\n",
    "    def __init__(self):\n",
    "        self._queue = []\n",
    "    \n",
    "    def enqueue(self, data): # enqueue\n",
    "        self._queue.append(data)\n",
    "        \n",
    "    def dequeue(self): #dequeue\n",
    "        if self._queue:\n",
    "            return self._queue.pop(0)\n",
    "        return \"Empty!\"\n",
    "    \n",
    "    def peek(self):\n",
    "        if self._queue:\n",
    "            return self._queue[0]\n",
    "        return \"Empty!\"\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self._queue)\n",
    "    \n",
    "    def display(self):\n",
    "        return self._queue\n",
    "    \n",
    "# Test\n",
    "from ds_backup.ds_tests import LinearQueue_Test\n",
    "LinearQueue_Test(LinearQueue)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90c17a22",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "585051b3",
   "metadata": {},
   "source": [
    "## Queue\n",
    "> First In - First Out (FIFO)\n",
    "\n",
    "## Circular\n",
    "\n",
    "### Main Methods\n",
    "- **enqueue / dequeue**: `enqueue` adds an element to the rear of the queue, `dequeue` removes an element from the front of the queue\n",
    "\n",
    "### Side Methods\n",
    "- **empty / full**: Check if the circular queue is empty or full, respectively.\n",
    "- **update_tail / update_head**: Update the tail or head pointers of the circular queue after enqueue or dequeue operations.\n",
    "- **head_at / tail_at**: Retrieve the value at the head or tail of the circular queue without removing it.\n",
    "- **size_of / max_size_of**: Get the current size or maximum size of the circular queue.\n",
    "- **display**: Display the elements of the circular queue in the order they are stored.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3c66d752",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List: [33, 23, 60, 47, 35, 46, 24, 93, 55, 22]\n",
      "\n",
      ">>> CQ\n",
      "Max_size: 9\n",
      "\n",
      "---START\n",
      "Status | Size | Head | Tail | Circular Queue\n",
      "Empty  |  0   |  0   |  0   | [None, None, None, None, None, None, None, None, None]\n",
      "\n",
      "---ENQUEUE\n",
      "Status | Size | Head | Tail | Circular Queue\n",
      "  33   |  1   |  0   |  1   | [33, None, None, None, None, None, None, None, None]\n",
      "  23   |  2   |  0   |  2   | [33, 23, None, None, None, None, None, None, None]\n",
      "  60   |  3   |  0   |  3   | [33, 23, 60, None, None, None, None, None, None]\n",
      "  47   |  4   |  0   |  4   | [33, 23, 60, 47, None, None, None, None, None]\n",
      "  35   |  5   |  0   |  5   | [33, 23, 60, 47, 35, None, None, None, None]\n",
      "  46   |  6   |  0   |  6   | [33, 23, 60, 47, 35, 46, None, None, None]\n",
      "  24   |  7   |  0   |  7   | [33, 23, 60, 47, 35, 46, 24, None, None]\n",
      "  93   |  8   |  0   |  8   | [33, 23, 60, 47, 35, 46, 24, 93, None]\n",
      "  55   |  9   |  0   |  0   | [33, 23, 60, 47, 35, 46, 24, 93, 55]\n",
      " Full  |  9   |  0   |  0   | [33, 23, 60, 47, 35, 46, 24, 93, 55]\n",
      "\n",
      "---DEQUEUE\n",
      "Status | Size | Head | Tail | Circular Queue\n",
      "  33   |  8   |  1   |  0   | [None, 23, 60, 47, 35, 46, 24, 93, 55]\n",
      "  23   |  7   |  2   |  0   | [None, None, 60, 47, 35, 46, 24, 93, 55]\n",
      "  60   |  6   |  3   |  0   | [None, None, None, 47, 35, 46, 24, 93, 55]\n",
      "  47   |  5   |  4   |  0   | [None, None, None, None, 35, 46, 24, 93, 55]\n",
      "\n",
      "---ENQUEUE\n",
      "Status | Size | Head | Tail | Circular Queue\n",
      "  35   |  6   |  4   |  1   | [35, None, None, None, 35, 46, 24, 93, 55]\n",
      "  46   |  7   |  4   |  2   | [35, 46, None, None, 35, 46, 24, 93, 55]\n",
      "  24   |  8   |  4   |  3   | [35, 46, 24, None, 35, 46, 24, 93, 55]\n",
      "  93   |  9   |  4   |  4   | [35, 46, 24, 93, 35, 46, 24, 93, 55]\n",
      " Full  |  9   |  4   |  4   | [35, 46, 24, 93, 35, 46, 24, 93, 55]\n",
      "\n",
      "---DEQUEUE\n",
      "Status | Size | Head | Tail | Circular Queue\n",
      "  35   |  8   |  5   |  4   | [35, 46, 24, 93, None, 46, 24, 93, 55]\n",
      "  46   |  7   |  6   |  4   | [35, 46, 24, 93, None, None, 24, 93, 55]\n",
      "  24   |  6   |  7   |  4   | [35, 46, 24, 93, None, None, None, 93, 55]\n",
      "  93   |  5   |  8   |  4   | [35, 46, 24, 93, None, None, None, None, 55]\n",
      "  55   |  4   |  0   |  4   | [35, 46, 24, 93, None, None, None, None, None]\n",
      "  35   |  3   |  1   |  4   | [None, 46, 24, 93, None, None, None, None, None]\n",
      "  46   |  2   |  2   |  4   | [None, None, 24, 93, None, None, None, None, None]\n",
      "  24   |  1   |  3   |  4   | [None, None, None, 93, None, None, None, None, None]\n",
      "  93   |  0   |  4   |  4   | [None, None, None, None, None, None, None, None, None]\n",
      "\n",
      "---END\n",
      "Status | Size | Head | Tail | Circular Queue\n",
      "Empty  |  0   |  4   |  4   | [None, None, None, None, None, None, None, None, None]\n"
     ]
    }
   ],
   "source": [
    "# Circular Queue\n",
    "class CircularQueue:\n",
    "    def __init__(self, max_size, start=0):\n",
    "        self._queue = [None]*max_size\n",
    "        self._max_size = max_size\n",
    "        self._size = 0\n",
    "        self._head = self._tail = start\n",
    "    \n",
    "    def empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def full(self):\n",
    "        return self._size == self._max_size\n",
    "    \n",
    "    def update_tail(self):\n",
    "        self._tail = (self._tail + 1) % self._max_size\n",
    "    \n",
    "    def update_head(self):\n",
    "        self._head = (self._head + 1) % self._max_size\n",
    "        \n",
    "    def enqueue(self, data): # enqueue\n",
    "        if self.full():\n",
    "            return \"Full\"\n",
    "\n",
    "        # Put item into queue\n",
    "        self._queue[self._tail] = data\n",
    "        self._size += 1\n",
    "        self.update_tail()\n",
    "        \n",
    "        # To check\n",
    "        return data\n",
    "    \n",
    "    def dequeue(self): # dequeue\n",
    "        if self.empty():\n",
    "            return \"Empty\"\n",
    "        \n",
    "        # Remove item from queue\n",
    "        data = self._queue[self._head]\n",
    "        self._queue[self._head] = None\n",
    "        self._size -= 1\n",
    "        self.update_head()\n",
    "        \n",
    "        # To check\n",
    "        return data\n",
    "    \n",
    "    def head_at(self):\n",
    "        return self._head\n",
    "    \n",
    "    def tail_at(self):\n",
    "        return self._tail\n",
    "    \n",
    "    def max_size_of(self):\n",
    "        return self._max_size\n",
    "    \n",
    "    def size_of(self):\n",
    "        return self._size\n",
    "    \n",
    "    def display(self):\n",
    "        return self._queue\n",
    "    \n",
    "# Test\n",
    "from ds_backup.ds_tests import CircularQueue_Test\n",
    "CircularQueue_Test(CircularQueue)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2f9e565",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfcc11e3",
   "metadata": {},
   "source": [
    "## Binary Search Tree\n",
    "\n",
    "A binary search tree (BST) is a hierarchical data structure where each node has at most two children. The left child of a node contains values smaller than the parent node, while the right child contains values greater than the parent node. This property holds true recursively for all nodes in the tree, down to the leaf nodes.\n",
    "\n",
    "### Main Methods\n",
    "- **put**: Adds a new node with a given value to the BST, maintaining the binary search tree property.\n",
    "- **find**: Searches for a node with a specified value in the BST and returns True if found, or False otherwise.\n",
    "- **traversals (inorder, preorder, postorder)**: Perform different ways of traversing the BST to visit and process nodes in a specific order.\n",
    "\n",
    "### Side Methods\n",
    "- **min_ / max_**: Find the minimum or maximum value in the BST by traversing to the leftmost or rightmost node, respectively.\n",
    "- **height**: Calculates the height of the BST, which is the maximum depth of the tree (the number of edges on the longest path from the root to a leaf node).\n",
    "- **size**: Returns the number of nodes in the BST.\n",
    "\n",
    "Note: The deletion operation is not included in this description. Implementing deletion in a BST can be more complex and involves handling various cases based on the structure of the tree.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "0985a0fb",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List: [15, 26, 91, 63, 84, 33]\n",
      "Sorted: [15, 26, 33, 63, 84, 91]\n",
      "\n",
      ">>> BST:\n",
      "AFTER INSERTION:\n",
      "Size: 6 | True\n",
      "Height: 4 | idk how to display this\n",
      "Min: 15 | True\n",
      "Max: 91 | True\n",
      "\n",
      "Sampled from lst: [(33, True), (63, True), (84, True), (91, True), (15, True)] | True\n",
      "Random: [(78, False), (29, False), (46, False), (75, False), (54, False)]\n",
      "\n",
      "Inord: [15, 26, 33, 63, 84, 91] | True\n",
      "Preord: [15, 26, 91, 63, 33, 84]\n",
      "Postord: [33, 84, 63, 91, 26, 15]\n"
     ]
    }
   ],
   "source": [
    "# Binary Search Tree\n",
    "class Node: # Node\n",
    "    def __init__(self, data, start=None):\n",
    "        self.data = data\n",
    "        self.left = self.right = start\n",
    "\n",
    "class BinarySearchTree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "\n",
    "    # Insert a node\n",
    "    def put(self, data):\n",
    "        if self.root is None: # BST empty\n",
    "            self.root = Node(data)\n",
    "        else:\n",
    "            curr = self.root # initialise curr pointer\n",
    "            while curr:\n",
    "                if data < curr.data: # data put at left\n",
    "                    if curr.left:\n",
    "                        curr = curr.left\n",
    "                    else: # no left child\n",
    "                        curr.left = Node(data)\n",
    "                        break\n",
    "                else: # data put at right\n",
    "                    if curr.right:\n",
    "                        curr = curr.right\n",
    "                    else:  # no right child\n",
    "                        curr.right = Node(data)\n",
    "                        break   \n",
    "                        \n",
    "    def find(self, data):\n",
    "        curr = self.root   # start from root\n",
    "        while curr:\n",
    "            if data < curr.data:  # data at left\n",
    "                curr = curr.left\n",
    "            elif data > curr.data:    # data at right\n",
    "                curr = curr.right\n",
    "            else:\n",
    "                return True # found\n",
    "        return False\n",
    "    \n",
    "    def min_of(self):\n",
    "        curr = self.root # start from root\n",
    "        while curr.left:\n",
    "            curr = curr.left # keep going left\n",
    "        return curr.data\n",
    "        \n",
    "    def max_of(self):\n",
    "        curr = self.root # start from root\n",
    "        while curr.right:\n",
    "            curr = curr.right # keep going right\n",
    "        return curr.data\n",
    "    \n",
    "    def size(self):\n",
    "        def go(node): # helper\n",
    "            if node:\n",
    "                return 1 + go(node.left) + go(node.right)\n",
    "            return 0\n",
    "        return go(self.root)   \n",
    "    \n",
    "    def height(self):\n",
    "        def go(node): # helper\n",
    "            if node:\n",
    "                return 1 + max(go(node.left), go(node.right))\n",
    "            return -1 # it has -1 if empty\n",
    "        return go(self.root)\n",
    "\n",
    "        \n",
    "    # In_order\n",
    "    def in_order(self):\n",
    "        lst = [] # results\n",
    "        def go(node): # helper\n",
    "            nonlocal lst\n",
    "            if node: # If node exists\n",
    "                go(node.left) # left\n",
    "                lst.append(node.data) # Node\n",
    "                go(node.right) # Right\n",
    "        go(self.root)\n",
    "        return lst\n",
    "    \n",
    "    # Pre_order\n",
    "    def pre_order(self):\n",
    "        lst = [] # results\n",
    "        def go(node): # helper\n",
    "            nonlocal lst\n",
    "            if node: # If node exists\n",
    "                lst.append(node.data) # Node\n",
    "                go(node.left) # left\n",
    "                go(node.right) # Right\n",
    "        go(self.root)\n",
    "        return lst\n",
    "    \n",
    "    # Post_order\n",
    "    def post_order(self):\n",
    "        lst = [] # results\n",
    "        def go(node): # helper\n",
    "            nonlocal lst\n",
    "            if node: # If node exists\n",
    "                go(node.left) # left\n",
    "                go(node.right) # Right\n",
    "                lst.append(node.data) # Node\n",
    "        go(self.root)\n",
    "        return lst\n",
    "\n",
    "# Test\n",
    "from ds_backup.ds_tests import BinarySearchTree_Test\n",
    "BinarySearchTree_Test(BinarySearchTree)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}