{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "eb4e80c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# binary search tree data structure\n",
    "#\n",
    "# we are using the same data structure a) for a tree and b) for a node in that tree\n",
    "#\n",
    "# note that this is a sorted data structure:\n",
    "# for each node in the tree (including the root node), our implementation needs to make sure that\n",
    "#    a) all items within the self._left subtree are smaller than self._item\n",
    "#    b) all items within the self._right subtree are greater than or equal to self._item\n",
    "#\n",
    "# this contains very basic features only, and will require a few extensions to become usable;\n",
    "# e.g., a method needs to be added to delete elements while remaining sorted\n",
    "#\n",
    "class BinarySearchTree:\n",
    "    def __init__(self):\n",
    "        self._left = None\n",
    "        self._item = None\n",
    "        self._right = None\n",
    "\n",
    "    def get_root_item(self):\n",
    "        return self._item\n",
    "    \n",
    "    # returns True if the tree contains value, False otherwise\n",
    "    #\n",
    "    def contains(self, value):\n",
    "        return self._find_node(value) is not None\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._item is None\n",
    "    \n",
    "    # returns the number of nodes in the tree\n",
    "    #\n",
    "    def get_size(self):\n",
    "        if self._item is None:\n",
    "            return 0\n",
    "        size = 1\n",
    "        if self._left is not None:\n",
    "            size += self._left.get_size()\n",
    "        if self._right is not None:\n",
    "            size += self._right.get_size()\n",
    "        return size\n",
    "\n",
    "    # returns the smallest value stored in the tree data structure\n",
    "    #\n",
    "    def get_smallest(self):\n",
    "        if self._left is None:\n",
    "            return self._item\n",
    "        else:\n",
    "            return self._left.get_smallest()\n",
    "        \n",
    "    # returns the greatest value stored in the tree data structure\n",
    "    #\n",
    "    def get_greatest(self):\n",
    "        if self._right is None:\n",
    "            return self._item\n",
    "        else:\n",
    "            return self._right.get_greatest()\n",
    "    \n",
    "    # removes all content from the tree\n",
    "    #\n",
    "    def clear(self):\n",
    "        if self._left is not None:\n",
    "            self._left.clear()\n",
    "        if self._right is not None:\n",
    "            self._right.clear()\n",
    "        self._left = None\n",
    "        self._item = None\n",
    "        self._right = None\n",
    "    \n",
    "    # attach an additional node to the tree, containing the value passed as an argument\n",
    "    #\n",
    "    # if the tree already contains the value, it will be added nonetheless\n",
    "    #\n",
    "    def insert(self, value):\n",
    "        if self._item is None:\n",
    "            self._item = value\n",
    "        elif value < self._item:\n",
    "            if self._left is None:\n",
    "                self._left = BinarySearchTree()\n",
    "                self._left._item = value\n",
    "            else:\n",
    "                self._left.insert(value)\n",
    "        else:\n",
    "            if self._right is None:\n",
    "                self._right = BinarySearchTree()\n",
    "                self._right._item = value\n",
    "            else:\n",
    "                self._right.insert(value)\n",
    "    \n",
    "    # replaces the content of self with the content of a dyn. array (Python list)\n",
    "    #\n",
    "    def copy_from_dynarray(self, dynarray):\n",
    "        self.clear()\n",
    "        for el in dynarray:\n",
    "            self.insert(el)\n",
    "    \n",
    "    # traversal of the binary search tree\n",
    "    #\n",
    "    # appends the content of self, in ascending order, to a Python list (dyn. array)\n",
    "    #\n",
    "    def append_to_dynarray(self, dynarray):\n",
    "        if self._left is not None:\n",
    "            self._left.append_to_dynarray(dynarray)\n",
    "        dynarray.append(self._item)\n",
    "        if self._right is not None:\n",
    "            self._right.append_to_dynarray(dynarray)\n",
    "    \n",
    "    # returns a string representing the tree structure\n",
    "    #\n",
    "    def to_string(self):\n",
    "        if self._item is None:\n",
    "            return \"[]\"\n",
    "        if self._left is None and self._right is None:\n",
    "            return str(self._item)\n",
    "        content = str(self._item)\n",
    "        if self._left is not None:\n",
    "            content = content + \" -> [\" + self._left.to_string() + \"]\"\n",
    "        else:\n",
    "            content = content + \" -> []\"\n",
    "        if self._right is not None:\n",
    "            content = content + \", [\" + self._right.to_string() + \"]\"\n",
    "        else:\n",
    "            content = content + \", []\"\n",
    "        return content\n",
    "\n",
    "    # returns the/a node containing an item with a certain value\n",
    "    #\n",
    "    # if no such node exists, None is returned\n",
    "    #\n",
    "    def _find_node(self, value):\n",
    "        if self._item is None:\n",
    "            return None\n",
    "        elif self._item == value:\n",
    "            return self\n",
    "        elif value < self._item:\n",
    "            if self._left is None:\n",
    "                return None\n",
    "            else:\n",
    "                return self._left._find_node(value)\n",
    "        else:\n",
    "            if self._right is None:\n",
    "                return None\n",
    "            else:\n",
    "                return self._right._find_node(value)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "115a55d7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "test_tree: 7 -> [4 -> [3 -> [1], []], []], [25 -> [13 -> [], [23]], [111]]\n",
      "root node item: 7\n",
      "does the tree contain 13?: True\n",
      "test that the node with 13 is found: 13\n",
      "does the tree contain 12?: False\n",
      "test that _find_node(12) returns None: True\n"
     ]
    }
   ],
   "source": [
    "# minor test\n",
    "#\n",
    "test_tree = BinarySearchTree()\n",
    "test_tree.copy_from_dynarray([7, 4, 25, 3, 13, 23, 1, 111])\n",
    "print(\"test_tree:\", test_tree.to_string())\n",
    "\n",
    "print(\"root node item:\", test_tree.get_root_item())\n",
    "\n",
    "print(\"does the tree contain 13?:\", test_tree.contains(13))\n",
    "test_tree._find_node(13)\n",
    "print(\"test that the node with 13 is found:\", test_tree._find_node(13).get_root_item())\n",
    "\n",
    "print(\"does the tree contain 12?:\", test_tree.contains(12))\n",
    "test_tree._find_node(12)\n",
    "print(\"test that _find_node(12) returns None:\", test_tree._find_node(12) is None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "41448ac0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "test_list: [1, 3, 4, 7, 13, 23, 25, 111]\n"
     ]
    }
   ],
   "source": [
    "test_list = []\n",
    "test_tree.append_to_dynarray(test_list)\n",
    "print(\"test_list:\", test_list)"
   ]
  }
 ],
 "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}