Python_Data_Structures_Trees_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e5af2468-ace7-4e66-afe9-b2516e9ed172",
   "metadata": {},
   "source": [
    "# LinkedIn Learning\n",
    "# Python Data Structures --  Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "875d2b44-218a-4e73-b29a-3ff20a961874",
   "metadata": {},
   "source": [
    "## 2. Modifying Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "217bf66d-7819-4636-b708-c60f4b9fd2f4",
   "metadata": {},
   "source": [
    "### A. Adding Nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "1a16bd38-4c09-45b8-8a0c-1ce624e59641",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def search(self, target):\n",
    "        if self.data == target:\n",
    "            print(\"Found it!\")\n",
    "            return self\n",
    "        if self.left and self.data > target:\n",
    "            return self.left.search(target)\n",
    "        if self.right and self.data < target:\n",
    "            return self.right.search(target)\n",
    "        print(\"Value not found in tree\")\n",
    "\n",
    "    def add(self, data):\n",
    "        if self.data == data:\n",
    "            return \n",
    "        if data < self.data:\n",
    "            if self.left is None:\n",
    "                self.left = Node(data)\n",
    "            else:\n",
    "                self.left.add(data)\n",
    "        else:  # Ensuring BST property\n",
    "            if self.right is None:\n",
    "                self.right = Node(data)\n",
    "            else:\n",
    "                self.right.add(data)\n",
    "\n",
    "    def traversePreorder(self):\n",
    "        print(self.data, end=\" \")\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traverseInorder()\n",
    "        print(self.data, end=\" \")\n",
    "        if self.right:\n",
    "            self.right.traverseInorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePostorder() \n",
    "        if self.right:\n",
    "            self.right.traversePostorder()\n",
    "        print(self.data, end=\" \")\n",
    "        \n",
    "    def height(self, h=0):\n",
    "        leftHeight = self.left.height(h+1) if self.left else h\n",
    "        rightHeight = self.right.height(h+1) if self.right else h\n",
    "        return max(leftHeight, rightHeight)\n",
    "        \n",
    "    def getNodesAtDepth(self, depth, nodes=None):\n",
    "        if nodes is None:\n",
    "            nodes = []\n",
    "        if depth == 0:\n",
    "            nodes.append(self.data)\n",
    "            return nodes\n",
    "        if self.left:\n",
    "            self.left.getNodesAtDepth(depth-1, nodes)\n",
    "        if self.right:\n",
    "            self.right.getNodesAtDepth(depth-1, nodes)\n",
    "        return nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "eb841e3a-0cd2-45ae-85fa-adef467d89ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name=''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "\n",
    "    def add(self, data):\n",
    "        self.root.add(data)\n",
    "\n",
    "    def traversePreorder(self):\n",
    "        self.root.traversePreorder()\n",
    "        print()\n",
    "\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "        print()\n",
    "\n",
    "    def traversePostorder(self):\n",
    "        self.root.traversePostorder()\n",
    "        print()\n",
    "\n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "\n",
    "    def getNodesAtDepth(self, depth):\n",
    "        return self.root.getNodesAtDepth(depth)\n",
    "\n",
    "    def _nodeToChar(self, n, spacing):\n",
    "        if n is None:\n",
    "            return '_' + (' ' * spacing)\n",
    "        spacing = max(spacing - len(str(n)) + 1, 1)\n",
    "        return str(n) + (' ' * spacing)\n",
    "\n",
    "    def print(self, label=''):\n",
    "        print(self.name + ' ' + label)\n",
    "        height = self.root.height()\n",
    "        spacing = 3\n",
    "        width = int((2 ** height - 1) * (spacing + 1) + 1)\n",
    "        offset = int((width - 1) / 2)\n",
    "\n",
    "        for depth in range(0, height + 1):\n",
    "            if depth > 0:\n",
    "                print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\\\'] * (2 ** (depth - 1))))\n",
    "            row = self.root.getNodesAtDepth(depth, [])\n",
    "            print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))\n",
    "            spacing = offset + 1\n",
    "            offset = max(int(offset / 2) - 1, 0)\n",
    "        print()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "26795eea-dc52-475f-b9bb-5d4b7935293a",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_1 = Tree(Node(50))\n",
    "tree_1.add(25)\n",
    "tree_1.add(75)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "93e97810-796a-4987-9fac-0dc164a63316",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "  50  \n",
      " / \\\n",
      "25  75  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_1.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "53a4d550-9e71-482a-9c68-531c2585dec1",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_1.add(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "83443f8f-ec5c-429a-8819-a6496042851c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "      50  \n",
      "   /     \\\n",
      "  25      75      \n",
      " / \\     / \\\n",
      "10  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_1.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "533a79bb-cf33-4045-ad09-1ff78b6a960d",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_1.add(76)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "d43eacd1-af55-41e3-88e2-04e9052d01b9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "      50  \n",
      "   /     \\\n",
      "  25      75      \n",
      " / \\     / \\\n",
      "10  76  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_1.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "bccbd10b-f6ce-484b-bcde-07d1f5a86716",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_1.add(75)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "f9b30aad-17cf-42df-8631-f7250ca47196",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "      50  \n",
      "   /     \\\n",
      "  25      75      \n",
      " / \\     / \\\n",
      "10  76  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_1.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "d1b279ff-ad30-47ca-9a7a-eabe497cbab8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Preorder Traversal:\n",
      "50 25 10 75 76 \n"
     ]
    }
   ],
   "source": [
    "print(\"Preorder Traversal:\")\n",
    "tree_1.traversePreorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "917e12b0-6d9b-4e37-b645-4120ce5db51e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Inorder Traversal:\n",
      "10 25 50 75 76 \n"
     ]
    }
   ],
   "source": [
    "print(\"Inorder Traversal:\")\n",
    "tree_1.traverseInorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "6fcb89a0-191a-4429-8001-60dd7da90ca0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Postorder Traversal:\n",
      "10 25 76 75 50 \n"
     ]
    }
   ],
   "source": [
    "print(\"Postorder Traversal:\")\n",
    "tree_1.traversePostorder()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2748360d-dec7-457e-8c2b-2a72f08d84dc",
   "metadata": {},
   "source": [
    "### B. Deleting Nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "567280b3-bc0d-41eb-8c79-d272e925bdd0",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def search(self, target):\n",
    "        if self.data == target:\n",
    "            print(\"Found it!\")\n",
    "            return self\n",
    "        if self.left and self.data > target:\n",
    "            return self.left.search(target)\n",
    "        if self.right and self.data < target:\n",
    "            return self.right.search(target)\n",
    "        print(\"Value not found in tree\")\n",
    "\n",
    "    def add(self, data):\n",
    "        if self.data == data:\n",
    "            return \n",
    "        if data < self.data:\n",
    "            if self.left is None:\n",
    "                self.left = Node(data)\n",
    "            else:\n",
    "                self.left.add(data)\n",
    "        else:  # Ensuring BST property\n",
    "            if self.right is None:\n",
    "                self.right = Node(data)\n",
    "            else:\n",
    "                self.right.add(data)\n",
    "\n",
    "    def traversePreorder(self):\n",
    "        print(self.data, end=\" \")\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traverseInorder()\n",
    "        print(self.data, end=\" \")\n",
    "        if self.right:\n",
    "            self.right.traverseInorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePostorder() \n",
    "        if self.right:\n",
    "            self.right.traversePostorder()\n",
    "        print(self.data, end=\" \")\n",
    "        \n",
    "    def height(self, h=0):\n",
    "        leftHeight = self.left.height(h+1) if self.left else h\n",
    "        rightHeight = self.right.height(h+1) if self.right else h\n",
    "        return max(leftHeight, rightHeight)\n",
    "        \n",
    "    def getNodesAtDepth(self, depth, nodes=None):\n",
    "        if nodes is None:\n",
    "            nodes = []\n",
    "        if depth == 0:\n",
    "            nodes.append(self.data)\n",
    "            return nodes\n",
    "        if self.left:\n",
    "            self.left.getNodesAtDepth(depth-1, nodes)\n",
    "        if self.right:\n",
    "            self.right.getNodesAtDepth(depth-1, nodes)\n",
    "        return nodes\n",
    "\n",
    "    def findMin(self):\n",
    "        if self.left:\n",
    "            return self.left.findMin()\n",
    "        return self.data\n",
    "    \n",
    "    def delete(self, target):\n",
    "        if self.data == target: \n",
    "            # Do the deletion here\n",
    "            if self.left and self.right:\n",
    "                # RTFM\n",
    "                minValue = self.right.findMin()\n",
    "                self.data = minValue\n",
    "                self.right = self.right.delete(minValue)\n",
    "                return self\n",
    "            else:\n",
    "                return self.left or self.right\n",
    "                \n",
    "        if self.right and target > self.data:\n",
    "            self.right = self.right.delete(target)\n",
    "        if self.left and target < self.data:\n",
    "            self.left = self.left.delete(target)\n",
    "        return self"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "7c7ca4c0-80cb-4d2b-9910-d59194c94560",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name=''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "\n",
    "    def add(self, data):\n",
    "        self.root.add(data)\n",
    "\n",
    "    #def traversePreorder(self):\n",
    "       # self.root.traversePreorder()\n",
    "       # print()\n",
    "\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "        print()\n",
    "\n",
    "    #def traversePostorder(self):\n",
    "        #self.root.traversePostorder()\n",
    "        #print()\n",
    "\n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "\n",
    "    def getNodesAtDepth(self, depth):\n",
    "        return self.root.getNodesAtDepth(depth)\n",
    "\n",
    "    def _nodeToChar(self, n, spacing):\n",
    "        if n is None:\n",
    "            return '_' + (' ' * spacing)\n",
    "        spacing = max(spacing - len(str(n)) + 1, 1)\n",
    "        return str(n) + (' ' * spacing)\n",
    "\n",
    "    def print(self, label=''):\n",
    "        print(self.name + ' ' + label)\n",
    "        height = self.root.height()\n",
    "        spacing = 3\n",
    "        width = int((2 ** height - 1) * (spacing + 1) + 1)\n",
    "        offset = int((width - 1) / 2)\n",
    "\n",
    "        for depth in range(0, height + 1):\n",
    "            if depth > 0:\n",
    "                print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\\\'] * (2 ** (depth - 1))))\n",
    "            row = self.root.getNodesAtDepth(depth, [])\n",
    "            print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))\n",
    "            spacing = offset + 1\n",
    "            offset = max(int(offset / 2) - 1, 0)\n",
    "        print()\n",
    "\n",
    "    def delete(self, target):\n",
    "        self.root = self.root.delete(target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "d67f4000-fbf8-4f85-b00b-b5a839d4b67a",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_2 = Tree(Node(50))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "978161aa-176f-4e6f-ab48-7c6fce882855",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_2.root.left = Node(25)\n",
    "tree_2.root.right = Node(75)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "9f5c5131-a5b0-4745-b807-05481ae30cc6",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_2.root.right.left = Node(67)\n",
    "tree_2.root.right.right = Node(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "ccadf5b7-7f8e-4164-bd5a-71ee2ee4e53b",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_2.root.right.right.right = Node(120)\n",
    "tree_2.root.right.right.left = Node(80)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "e943eea0-edaa-4f6e-8cfd-a82edcb69f06",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_2.root.right.right.left.right = Node(92)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "e227667a-ecc5-4152-ae5d-2e68d4fc37b2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "                              50  \n",
      "               /                             \\\n",
      "              25                              75                              \n",
      "       /             \\                 /             \\\n",
      "      67              100             \n",
      "   /     \\         /     \\         /     \\         /     \\\n",
      "  80      120     \n",
      " / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\\n",
      "92  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_2.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "40566131-f294-42d4-80f6-e7175e4d9f28",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Inorder Traversal of BST:\n",
      "25 50 67 75 80 92 100 120 \n"
     ]
    }
   ],
   "source": [
    "print(\"Inorder Traversal of BST:\")\n",
    "tree_2.traverseInorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "9298b9cc-15c6-4ba2-bef5-0d8124c722e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_2.delete(75)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "37b9fac8-1c1a-41b6-a6d0-d97f74ee4879",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "              50  \n",
      "       /             \\\n",
      "      25              80              \n",
      "   /     \\         /     \\\n",
      "  67      100     \n",
      " / \\     / \\     / \\     / \\\n",
      "92  120 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_2.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "08cbeb5f-007b-4319-95f0-74cc8eda90c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_2.delete(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "8968b60c-74fc-473a-9d4f-fee40f90dabf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "              67  \n",
      "       /             \\\n",
      "      25              80              \n",
      "   /     \\         /     \\\n",
      "  100     \n",
      " / \\     / \\     / \\     / \\\n",
      "92  120 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_2.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "702f6e14-8a6b-49d9-84fa-e1bfb4b0380d",
   "metadata": {},
   "source": [
    "### C. Detecting Unbalanced tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "338b5e35-03ac-4ccf-872e-7c33fd924fc4",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def search(self, target):\n",
    "        if self.data == target:\n",
    "            print(\"Found it!\")\n",
    "            return self\n",
    "        if self.left and self.data > target:\n",
    "            return self.left.search(target)\n",
    "        if self.right and self.data < target:\n",
    "            return self.right.search(target)\n",
    "        print(\"Value not found in tree\")\n",
    "\n",
    "    def add(self, data):\n",
    "        if self.data == data:\n",
    "            return \n",
    "        if data < self.data:\n",
    "            if self.left is None:\n",
    "                self.left = Node(data)\n",
    "            else:\n",
    "                self.left.add(data)\n",
    "        else:  # Ensuring BST property\n",
    "            if self.right is None:\n",
    "                self.right = Node(data)\n",
    "            else:\n",
    "                self.right.add(data)\n",
    "\n",
    "    def traversePreorder(self):\n",
    "        print(self.data, end=\" \")\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traverseInorder()\n",
    "        print(self.data, end=\" \")\n",
    "        if self.right:\n",
    "            self.right.traverseInorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePostorder() \n",
    "        if self.right:\n",
    "            self.right.traversePostorder()\n",
    "        print(self.data, end=\" \")\n",
    "        \n",
    "    def height(self, h=0):\n",
    "        leftHeight = self.left.height(h+1) if self.left else h\n",
    "        rightHeight = self.right.height(h+1) if self.right else h\n",
    "        return max(leftHeight, rightHeight)\n",
    "        \n",
    "    def getNodesAtDepth(self, depth, nodes=None):\n",
    "        if nodes is None:\n",
    "            nodes = []\n",
    "        if depth == 0:\n",
    "            nodes.append(self.data)\n",
    "            return nodes\n",
    "        if self.left:\n",
    "            self.left.getNodesAtDepth(depth-1, nodes)\n",
    "        if self.right:\n",
    "            self.right.getNodesAtDepth(depth-1, nodes)\n",
    "        return nodes\n",
    "\n",
    "    def findMin(self):\n",
    "        if self.left:\n",
    "            return self.left.findMin()\n",
    "        return self.data\n",
    "    \n",
    "    def delete(self, target):\n",
    "        if self.data == target: \n",
    "            # Do the deletion here\n",
    "            if self.left and self.right:\n",
    "                # RTFM\n",
    "                minValue = self.right.findMin()\n",
    "                self.data = minValue\n",
    "                self.right = self.right.delete(minValue)\n",
    "                return self\n",
    "            else:\n",
    "                return self.left or self.right\n",
    "                \n",
    "        if self.right and target > self.data:\n",
    "            self.right = self.right.delete(target)\n",
    "        if self.left and target < self.data:\n",
    "            self.left = self.left.delete(target)\n",
    "        return self\n",
    "\n",
    "    def isBalanced(self):\n",
    "        leftHeight = self.left.height() + 1 if self.left else 0\n",
    "        rightHeight = self.right.height() + 1 if self.right else 0\n",
    "        return abs(leftHeight - rightHeight) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "4372e498-8857-4247-84c4-0a7875b43efd",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name=''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "\n",
    "    def add(self, data):\n",
    "        self.root.add(data)\n",
    "\n",
    "    #def traversePreorder(self):\n",
    "       # self.root.traversePreorder()\n",
    "       # print()\n",
    "\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "        print()\n",
    "\n",
    "    #def traversePostorder(self):\n",
    "        #self.root.traversePostorder()\n",
    "        #print()\n",
    "\n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "\n",
    "    def getNodesAtDepth(self, depth):\n",
    "        return self.root.getNodesAtDepth(depth)\n",
    "\n",
    "    def _nodeToChar(self, n, spacing):\n",
    "        if n is None:\n",
    "            return '_' + (' ' * spacing)\n",
    "        spacing = max(spacing - len(str(n)) + 1, 1)\n",
    "        return str(n) + (' ' * spacing)\n",
    "\n",
    "    def print(self, label=''):\n",
    "        print(self.name + ' ' + label)\n",
    "        height = self.root.height()\n",
    "        spacing = 3\n",
    "        width = int((2 ** height - 1) * (spacing + 1) + 1)\n",
    "        offset = int((width - 1) / 2)\n",
    "\n",
    "        for depth in range(0, height + 1):\n",
    "            if depth > 0:\n",
    "                print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\\\'] * (2 ** (depth - 1))))\n",
    "            row = self.root.getNodesAtDepth(depth, [])\n",
    "            print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))\n",
    "            spacing = offset + 1\n",
    "            offset = max(int(offset / 2) - 1, 0)\n",
    "        print()\n",
    "\n",
    "    def delete(self, target):\n",
    "        self.root = self.root.delete(target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "d8238e27-f1a9-413a-bc0b-57c4be32efe0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "An Unbalanced Tree \n",
      "              50  \n",
      "       /             \\\n",
      "      25              75              \n",
      "   /     \\         /     \\\n",
      "  100     \n",
      " / \\     / \\     / \\     / \\\n",
      "150 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_3 = Tree(Node(50), 'An Unbalanced Tree')\n",
    "tree_3.root.left = Node(25)\n",
    "tree_3.root.right = Node(75)\n",
    "tree_3.root.right.right = Node(100)\n",
    "tree_3.root.right.right.right = Node(150)\n",
    "tree_3.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "bbeab01b-7e89-4d42-9b46-850cf6669c0b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "print(tree_3.root.isBalanced())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "001840e8-2365-4762-990d-747f90b64a18",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(tree_3.root.left.isBalanced())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "a87a91d8-ca21-44db-81c4-7f91b72787d7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "print(tree_3.root.right.isBalanced())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa35a262-840c-42ab-abd8-095c102f5fea",
   "metadata": {},
   "source": [
    "### D. Challenge 2 --> Adding a balance Indicator to the printed tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "55ffccd3-0988-4667-b7dc-952d2003bf11",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def search(self, target):\n",
    "        if self.data == target:\n",
    "            print(\"Found it!\")\n",
    "            return self\n",
    "        if self.left and self.data > target:\n",
    "            return self.left.search(target)\n",
    "        if self.right and self.data < target:\n",
    "            return self.right.search(target)\n",
    "        print(\"Value not found in tree\")\n",
    "\n",
    "    def add(self, data):\n",
    "        if self.data == data:\n",
    "            return \n",
    "        if data < self.data:\n",
    "            if self.left is None:\n",
    "                self.left = Node(data)\n",
    "            else:\n",
    "                self.left.add(data)\n",
    "        else:  # Ensuring BST property\n",
    "            if self.right is None:\n",
    "                self.right = Node(data)\n",
    "            else:\n",
    "                self.right.add(data)\n",
    "\n",
    "    def traversePreorder(self):\n",
    "        print(self.data, end=\" \")\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traverseInorder()\n",
    "        print(self.data, end=\" \")\n",
    "        if self.right:\n",
    "            self.right.traverseInorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePostorder() \n",
    "        if self.right:\n",
    "            self.right.traversePostorder()\n",
    "        print(self.data, end=\" \")\n",
    "        \n",
    "    def height(self, h=0):\n",
    "        leftHeight = self.left.height(h+1) if self.left else h\n",
    "        rightHeight = self.right.height(h+1) if self.right else h\n",
    "        return max(leftHeight, rightHeight)\n",
    "        \n",
    "    def getNodesAtDepth(self, depth, nodes=[]):\n",
    "        if depth == 0:\n",
    "            nodes.append(self)\n",
    "            return nodes\n",
    "            \n",
    "        if self.left:\n",
    "            self.left.getNodesAtDepth(depth-1, nodes)\n",
    "        else:\n",
    "            nodes.extend([None]*2**(depth-1))\n",
    "            \n",
    "        if self.right:\n",
    "            self.right.getNodesAtDepth(depth-1, nodes)\n",
    "        else:\n",
    "            nodes.extend([None]*2**(depth-1))\n",
    "        return nodes\n",
    "\n",
    "    def findMin(self):\n",
    "        if self.left:\n",
    "            return self.left.findMin()\n",
    "        return self.data\n",
    "    \n",
    "    def delete(self, target):\n",
    "        if self.data == target: \n",
    "            # Do the deletion here\n",
    "            if self.left and self.right:\n",
    "                # RTFM\n",
    "                minValue = self.right.findMin()\n",
    "                self.data = minValue\n",
    "                self.right = self.right.delete(minValue)\n",
    "                return self\n",
    "            else:\n",
    "                return self.left or self.right\n",
    "                \n",
    "        if self.right and target > self.data:\n",
    "            self.right = self.right.delete(target)\n",
    "        if self.left and target < self.data:\n",
    "            self.left = self.left.delete(target)\n",
    "        return self\n",
    "\n",
    "    def isBalanced(self):\n",
    "        leftHeight = self.left.height() + 1 if self.left else 0\n",
    "        rightHeight = self.right.height() + 1 if self.right else 0\n",
    "        return abs(leftHeight - rightHeight) < 2\n",
    "\n",
    "    def toStr(self):\n",
    "        if not self.isBalanced():\n",
    "            return str(self.data)+'*'\n",
    "        return str(self.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "2d1ffee7-20ea-4663-9b8a-37af2c073e0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name=''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "\n",
    "    def add(self, data):\n",
    "        self.root.add(data)\n",
    "\n",
    "    #def traversePreorder(self):\n",
    "       # self.root.traversePreorder()\n",
    "       # print()\n",
    "\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "        print()\n",
    "\n",
    "    #def traversePostorder(self):\n",
    "        #self.root.traversePostorder()\n",
    "        #print()\n",
    "\n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "\n",
    "    def getNodesAtDepth(self, depth):\n",
    "        return self.root.getNodesAtDepth(depth)\n",
    "\n",
    "    def _nodeToChar(self, n, spacing):\n",
    "        if n is None:\n",
    "            return '_' + (' ' * spacing)\n",
    "        spacing = spacing - len(n.toStr()) + 1\n",
    "        return n.toStr() + (' ' * spacing)\n",
    "\n",
    "    def print(self, label=''):\n",
    "        print(self.name + ' ' + label)\n",
    "        height = self.root.height()\n",
    "        spacing = 3\n",
    "        width = int((2 ** height - 1) * (spacing + 1) + 1)\n",
    "        offset = int((width - 1) / 2)\n",
    "\n",
    "        for depth in range(0, height + 1):\n",
    "            if depth > 0:\n",
    "                print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\\\'] * (2 ** (depth - 1))))\n",
    "            row = self.root.getNodesAtDepth(depth, [])\n",
    "            print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))\n",
    "            spacing = offset + 1\n",
    "            offset = max(int(offset / 2) - 1, 0)\n",
    "        print()\n",
    "\n",
    "    def delete(self, target):\n",
    "        self.root = self.root.delete(target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "392b76c0-74b7-441c-92fc-228cd4d46b20",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "An Unbalanced Tree \n",
      "              50* \n",
      "       /             \\\n",
      "      25              75*             \n",
      "   /     \\         /     \\\n",
      "  _       _       _       100     \n",
      " / \\     / \\     / \\     / \\\n",
      "_   _   _   _   _   _   _   150 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_4 = Tree(Node(50), 'An Unbalanced Tree')\n",
    "tree_4.root.left = Node(25)\n",
    "tree_4.root.right = Node(75)\n",
    "tree_4.root.right.right = Node(100)\n",
    "tree_4.root.right.right.right = Node(150)\n",
    "tree_4.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd30c466-844b-45e7-8631-844ba84960f2",
   "metadata": {},
   "source": [
    "## 3. Rebalancing Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3292342-a63e-41d3-a001-e36b53d2b94b",
   "metadata": {},
   "source": [
    "### A. Rotating Trees in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "ca3936b8-2314-491d-9172-dfca5a73affc",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def search(self, target):\n",
    "        if self.data == target:\n",
    "            print(\"Found it!\")\n",
    "            return self\n",
    "        if self.left and self.data > target:\n",
    "            return self.left.search(target)\n",
    "        if self.right and self.data < target:\n",
    "            return self.right.search(target)\n",
    "        print(\"Value not found in tree\")\n",
    "\n",
    "    def add(self, data):\n",
    "        if self.data == data:\n",
    "            return \n",
    "        if data < self.data:\n",
    "            if self.left is None:\n",
    "                self.left = Node(data)\n",
    "            else:\n",
    "                self.left.add(data)\n",
    "        else:  # Ensuring BST property\n",
    "            if self.right is None:\n",
    "                self.right = Node(data)\n",
    "            else:\n",
    "                self.right.add(data)\n",
    "\n",
    "    def traversePreorder(self):\n",
    "        print(self.data, end=\" \")\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traverseInorder()\n",
    "        print(self.data, end=\" \")\n",
    "        if self.right:\n",
    "            self.right.traverseInorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePostorder() \n",
    "        if self.right:\n",
    "            self.right.traversePostorder()\n",
    "        print(self.data, end=\" \")\n",
    "        \n",
    "    def height(self, h=0):\n",
    "        leftHeight = self.left.height(h+1) if self.left else h\n",
    "        rightHeight = self.right.height(h+1) if self.right else h\n",
    "        return max(leftHeight, rightHeight)\n",
    "        \n",
    "    def getNodesAtDepth(self, depth, nodes=[]):\n",
    "        if depth == 0:\n",
    "            nodes.append(self)\n",
    "            return nodes\n",
    "            \n",
    "        if self.left:\n",
    "            self.left.getNodesAtDepth(depth-1, nodes)\n",
    "        else:\n",
    "            nodes.extend([None]*2**(depth-1))\n",
    "            \n",
    "        if self.right:\n",
    "            self.right.getNodesAtDepth(depth-1, nodes)\n",
    "        else:\n",
    "            nodes.extend([None]*2**(depth-1))\n",
    "        return nodes\n",
    "\n",
    "    def findMin(self):\n",
    "        if self.left:\n",
    "            return self.left.findMin()\n",
    "        return self.data\n",
    "    \n",
    "    def delete(self, target):\n",
    "        if self.data == target: \n",
    "            # Do the deletion here\n",
    "            if self.left and self.right:\n",
    "                # RTFM\n",
    "                minValue = self.right.findMin()\n",
    "                self.data = minValue\n",
    "                self.right = self.right.delete(minValue)\n",
    "                return self\n",
    "            else:\n",
    "                return self.left or self.right\n",
    "                \n",
    "        if self.right and target > self.data:\n",
    "            self.right = self.right.delete(target)\n",
    "        if self.left and target < self.data:\n",
    "            self.left = self.left.delete(target)\n",
    "        return self\n",
    "\n",
    "    def isBalanced(self):\n",
    "        leftHeight = self.left.height() + 1 if self.left else 0\n",
    "        rightHeight = self.right.height() + 1 if self.right else 0\n",
    "        return abs(leftHeight - rightHeight) < 2\n",
    "\n",
    "    def toStr(self):\n",
    "        if not self.isBalanced():\n",
    "            return str(self.data)+'*'\n",
    "        return str(self.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "b8c6f4a6-ed6b-4f19-b8f4-b96ac1ceb28a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name=''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "\n",
    "    def add(self, data):\n",
    "        self.root.add(data)\n",
    "\n",
    "    #def traversePreorder(self):\n",
    "       # self.root.traversePreorder()\n",
    "       # print()\n",
    "\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "        print()\n",
    "\n",
    "    #def traversePostorder(self):\n",
    "        #self.root.traversePostorder()\n",
    "        #print()\n",
    "\n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "\n",
    "    def getNodesAtDepth(self, depth):\n",
    "        return self.root.getNodesAtDepth(depth)\n",
    "\n",
    "    def _nodeToChar(self, n, spacing):\n",
    "        if n is None:\n",
    "            return '_' + (' ' * spacing)\n",
    "        spacing = spacing - len(n.toStr()) + 1\n",
    "        return n.toStr() + (' ' * spacing)\n",
    "\n",
    "    def print(self, label=''):\n",
    "        print(self.name + ' ' + label)\n",
    "        height = self.root.height()\n",
    "        spacing = 3\n",
    "        width = int((2 ** height - 1) * (spacing + 1) + 1)\n",
    "        offset = int((width - 1) / 2)\n",
    "\n",
    "        for depth in range(0, height + 1):\n",
    "            if depth > 0:\n",
    "                print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\\\'] * (2 ** (depth - 1))))\n",
    "            row = self.root.getNodesAtDepth(depth, [])\n",
    "            print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))\n",
    "            spacing = offset + 1\n",
    "            offset = max(int(offset / 2) - 1, 0)\n",
    "        print()\n",
    "\n",
    "    def delete(self, target):\n",
    "        self.root = self.root.delete(target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "774a8a33-8ff2-4ee8-8baa-baeacd9bc774",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotateRight(root):\n",
    "    pivot = root.left \n",
    "    reattachNode = pivot.right \n",
    "    root.left = reattachNode\n",
    "    pivot.right = root\n",
    "    return pivot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "ec4bdd90-7854-48fa-8454-3191bd4482c1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UNBALANCED LEFT LEFT \n",
      "              30* \n",
      "       /             \\\n",
      "      20              _               \n",
      "   /     \\         /     \\\n",
      "  10      21      _       _       \n",
      " / \\     / \\     / \\     / \\\n",
      "9   11  _   _   _   _   _   _   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unbalancedLeftLeft = Tree(Node(30), 'UNBALANCED LEFT LEFT')\n",
    "unbalancedLeftLeft.root.left = Node(20)\n",
    "unbalancedLeftLeft.root.left.right = Node(21)\n",
    "unbalancedLeftLeft.root.left.left = Node(10)\n",
    "unbalancedLeftLeft.root.left.left.left = Node(9)\n",
    "unbalancedLeftLeft.root.left.left.right = Node(11)\n",
    "unbalancedLeftLeft.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "aaf46ee6-cdfe-4497-9643-7d2147b404c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "unbalancedLeftLeft.root = rotateRight(unbalancedLeftLeft.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "1e489df5-662a-4f39-b22f-f192331fdc5f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UNBALANCED LEFT LEFT \n",
      "      20  \n",
      "   /     \\\n",
      "  10      30      \n",
      " / \\     / \\\n",
      "9   11  21  _   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unbalancedLeftLeft.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "1f02bd2a-8e45-4d1f-ba31-1027b176885b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotateLeft(root):\n",
    "    pivot = root.right\n",
    "    reattachNode = pivot.left\n",
    "    root.right = reattachNode\n",
    "    pivot.left = root\n",
    "    return pivot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "id": "cd15a738-8e85-46fa-a839-bcf7aa78b972",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UNBALANCED RIGHT RIGHT \n",
      "              10* \n",
      "       /             \\\n",
      "      _               20              \n",
      "   /     \\         /     \\\n",
      "  _       _       19      30      \n",
      " / \\     / \\     / \\     / \\\n",
      "_   _   _   _   _   _   29  31  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unbalancedRightRight = Tree(Node(10), 'UNBALANCED RIGHT RIGHT')\n",
    "unbalancedRightRight.root.right = Node(20)\n",
    "unbalancedRightRight.root.right.left = Node(19)\n",
    "unbalancedRightRight.root.right.right = Node(30)\n",
    "unbalancedRightRight.root.right.right.left = Node(29)\n",
    "unbalancedRightRight.root.right.right.right = Node(31)\n",
    "unbalancedRightRight.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "id": "d6319245-6d70-4e8d-8c93-254965f9c723",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UNBALANCED RIGHT RIGHT \n",
      "      20  \n",
      "   /     \\\n",
      "  10      30      \n",
      " / \\     / \\\n",
      "_   19  29  31  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unbalancedRightRight.root = rotateLeft(unbalancedRightRight.root)\n",
    "unbalancedRightRight.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "628e1b35-dfd6-4b5a-9071-8bd7eb01b71b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UNBALANCED LEFT RIGHT \n",
      "              30* \n",
      "       /             \\\n",
      "      10              31              \n",
      "   /     \\         /     \\\n",
      "  9       20      _       _       \n",
      " / \\     / \\     / \\     / \\\n",
      "_   _   19  21  _   _   _   _   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unbalancedLeftRight = Tree(Node(30), 'UNBALANCED LEFT RIGHT')\n",
    "unbalancedLeftRight.root.right = Node(31)\n",
    "unbalancedLeftRight.root.left = Node(10)\n",
    "unbalancedLeftRight.root.left.right = Node(20)\n",
    "unbalancedLeftRight.root.left.left = Node(9)\n",
    "unbalancedLeftRight.root.left.right.left = Node(19)\n",
    "unbalancedLeftRight.root.left.right.right = Node(21)\n",
    "unbalancedLeftRight.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "id": "e14ba01f-697a-4847-bce4-f56cda32b718",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UNBALANCED LEFT RIGHT \n",
      "      20  \n",
      "   /     \\\n",
      "  10      30      \n",
      " / \\     / \\\n",
      "9   19  21  31  \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unbalancedLeftRight.root.left = rotateLeft(unbalancedLeftRight.root.left)\n",
    "unbalancedLeftRight.root = rotateRight(unbalancedLeftRight.root)\n",
    "unbalancedLeftRight.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "id": "f7ef55df-5e52-451d-a636-b42d47afd22f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UNBALANCED RIGHT LEFT \n",
      "              30* \n",
      "       /             \\\n",
      "      31              10              \n",
      "   /     \\         /     \\\n",
      "  _       _       20      9       \n",
      " / \\     / \\     / \\     / \\\n",
      "_   _   _   _   21  19  _   _   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unbalancedRightLeft = Tree(Node(30), 'UNBALANCED RIGHT LEFT')\n",
    "unbalancedRightLeft.root.left = Node(31)\n",
    "unbalancedRightLeft.root.right = Node(10)\n",
    "unbalancedRightLeft.root.right.left = Node(20)\n",
    "unbalancedRightLeft.root.right.right = Node(9)\n",
    "unbalancedRightLeft.root.right.left.right = Node(19)\n",
    "unbalancedRightLeft.root.right.left.left = Node(21)\n",
    "unbalancedRightLeft.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "id": "94f12c2a-cd29-4c83-baf5-444a71d3310b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "UNBALANCED RIGHT LEFT \n",
      "      20  \n",
      "   /     \\\n",
      "  30      10      \n",
      " / \\     / \\\n",
      "31  21  19  9   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "unbalancedRightLeft.root.right = rotateRight(unbalancedRightLeft.root.right)\n",
    "unbalancedRightLeft.root = rotateLeft(unbalancedRightLeft.root)\n",
    "unbalancedRightLeft.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03f4c616-a0bc-41d7-86d8-7d8bf34a1b82",
   "metadata": {},
   "source": [
    "### B. Fixing a tree with multiple points of Imbalance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "id": "4731364f-40ef-4148-8cb1-47a92aae71c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def search(self, target):\n",
    "        if self.data == target:\n",
    "            print(\"Found it!\")\n",
    "            return self\n",
    "        if self.left and self.data > target:\n",
    "            return self.left.search(target)\n",
    "        if self.right and self.data < target:\n",
    "            return self.right.search(target)\n",
    "        print(\"Value not found in tree\")\n",
    "\n",
    "    def add(self, data):\n",
    "        if self.data == data:\n",
    "            return \n",
    "        if data < self.data:\n",
    "            if self.left is None:\n",
    "                self.left = Node(data)\n",
    "            else:\n",
    "                self.left.add(data)\n",
    "        else:  # Ensuring BST property\n",
    "            if self.right is None:\n",
    "                self.right = Node(data)\n",
    "            else:\n",
    "                self.right.add(data)\n",
    "\n",
    "    def traversePreorder(self):\n",
    "        print(self.data, end=\" \")\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traverseInorder()\n",
    "        print(self.data, end=\" \")\n",
    "        if self.right:\n",
    "            self.right.traverseInorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePostorder() \n",
    "        if self.right:\n",
    "            self.right.traversePostorder()\n",
    "        print(self.data, end=\" \")\n",
    "        \n",
    "    def height(self, h=0):\n",
    "        leftHeight = self.left.height(h+1) if self.left else h\n",
    "        rightHeight = self.right.height(h+1) if self.right else h\n",
    "        return max(leftHeight, rightHeight)\n",
    "        \n",
    "    def getNodesAtDepth(self, depth, nodes=[]):\n",
    "        if depth == 0:\n",
    "            nodes.append(self)\n",
    "            return nodes\n",
    "            \n",
    "        if self.left:\n",
    "            self.left.getNodesAtDepth(depth-1, nodes)\n",
    "        else:\n",
    "            nodes.extend([None]*2**(depth-1))\n",
    "            \n",
    "        if self.right:\n",
    "            self.right.getNodesAtDepth(depth-1, nodes)\n",
    "        else:\n",
    "            nodes.extend([None]*2**(depth-1))\n",
    "        return nodes\n",
    "\n",
    "    def findMin(self):\n",
    "        if self.left:\n",
    "            return self.left.findMin()\n",
    "        return self.data\n",
    "    \n",
    "    def delete(self, target):\n",
    "        if self.data == target: \n",
    "            # Do the deletion here\n",
    "            if self.left and self.right:\n",
    "                # RTFM\n",
    "                minValue = self.right.findMin()\n",
    "                self.data = minValue\n",
    "                self.right = self.right.delete(minValue)\n",
    "                return self\n",
    "            else:\n",
    "                return self.left or self.right\n",
    "                \n",
    "        if self.right and target > self.data:\n",
    "            self.right = self.right.delete(target)\n",
    "        if self.left and target < self.data:\n",
    "            self.left = self.left.delete(target)\n",
    "        return self\n",
    "\n",
    "    def isBalanced(self):\n",
    "        leftHeight = self.left.height() + 1 if self.left else 0\n",
    "        rightHeight = self.right.height() + 1 if self.right else 0\n",
    "        return abs(leftHeight - rightHeight) < 2\n",
    "\n",
    "    def toStr(self):\n",
    "        if not self.isBalanced():\n",
    "            return str(self.data)+'*'\n",
    "        return str(self.data)\n",
    "\n",
    "    def getLeftRightHeightDifference(self):\n",
    "        leftHeight = self.left.height() + 1 if self.left else 0\n",
    "        rightHeight = self.right.height() + 1 if self.right else 0\n",
    "        return leftHeight - rightHeight\n",
    "        \n",
    "    def fixImbalanceIfExists(self):\n",
    "        if self.getLeftRightHeightDifference() > 1:\n",
    "            # Left Imbalance\n",
    "            if self.left.getLeftRightHeightDifference() > 0:\n",
    "                # Left Left Imbalance\n",
    "                return rotateRight(self)\n",
    "            else:\n",
    "                # Left Right Imbalance\n",
    "                self.left = rotateLeft(self.left)\n",
    "                return rotateRight(self)\n",
    "        elif self.getLeftRightHeightDifference() < -1:\n",
    "            #Right Imbalance\n",
    "            if self.right.getLeftRightHeightDifference() < 0:\n",
    "                # Right Right Imbalance\n",
    "                return rotateLeft(self)\n",
    "            else:\n",
    "                # Right Left Imbalance\n",
    "                self.right = rotateRight(self.right)\n",
    "                return rotateLeft(self)\n",
    "        return self\n",
    "\n",
    "    def rebalance(self):\n",
    "        if self.left:\n",
    "            self.left.rebalance()\n",
    "            self.left = self.left.fixImbalanceIfExists()\n",
    "        if self.right:\n",
    "            self.right.rebalance()\n",
    "            self.right = self.right.fixImbalanceIfExists()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "id": "e0555f9f-f6c5-4956-8d29-824c4626294d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name=''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "\n",
    "    def add(self, data):\n",
    "        self.root.add(data)\n",
    "\n",
    "    #def traversePreorder(self):\n",
    "       # self.root.traversePreorder()\n",
    "       # print()\n",
    "\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "        print()\n",
    "\n",
    "    #def traversePostorder(self):\n",
    "        #self.root.traversePostorder()\n",
    "        #print()\n",
    "\n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "\n",
    "    def getNodesAtDepth(self, depth):\n",
    "        return self.root.getNodesAtDepth(depth)\n",
    "\n",
    "    def _nodeToChar(self, n, spacing):\n",
    "        if n is None:\n",
    "            return '_' + (' ' * spacing)\n",
    "        spacing = spacing - len(n.toStr()) + 1\n",
    "        return n.toStr() + (' ' * spacing)\n",
    "\n",
    "    def print(self, label=''):\n",
    "        print(self.name + ' ' + label)\n",
    "        height = self.root.height()\n",
    "        spacing = 3\n",
    "        width = int((2 ** height - 1) * (spacing + 1) + 1)\n",
    "        offset = int((width - 1) / 2)\n",
    "\n",
    "        for depth in range(0, height + 1):\n",
    "            if depth > 0:\n",
    "                print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\\\'] * (2 ** (depth - 1))))\n",
    "            row = self.root.getNodesAtDepth(depth, [])\n",
    "            print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))\n",
    "            spacing = offset + 1\n",
    "            offset = max(int(offset / 2) - 1, 0)\n",
    "        print()\n",
    "\n",
    "    def delete(self, target):\n",
    "        self.root = self.root.delete(target)\n",
    "\n",
    "    def rebalance(self):\n",
    "        self.root.rebalance()\n",
    "        self.root = self.root.fixImbalanceIfExists()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "id": "981cfb87-bda3-475f-a633-36d8d513a97d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotateRight(root):\n",
    "    pivot = root.left \n",
    "    reattachNode = pivot.right \n",
    "    root.left = reattachNode\n",
    "    pivot.right = root\n",
    "    return pivot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "11635143-a246-412e-b6c2-863f6c7aaa62",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotateLeft(root):\n",
    "    pivot = root.right\n",
    "    reattachNode = pivot.left\n",
    "    root.right = reattachNode\n",
    "    pivot.left = root\n",
    "    return pivot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "id": "18845fbe-35ce-46f1-8df6-5d7338e27576",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "                                                              50* \n",
      "                               /                                                             \\\n",
      "                              25*                                                             75                                                              \n",
      "               /                             \\                                 /                             \\\n",
      "              10*                             35                              _                               _                               \n",
      "       /             \\                 /             \\                 /             \\                 /             \\\n",
      "      5*              13              30              _               _               _               _               _               \n",
      "   /     \\         /     \\         /     \\         /     \\         /     \\         /     \\         /     \\         /     \\\n",
      "  2       _       _       _       _       _       _       _       _       _       _       _       _       _       _       _       \n",
      " / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\\n",
      "1   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_5 = Tree(Node(50))\n",
    "tree_5.root.left = Node(25)\n",
    "tree_5.root.right = Node(75)\n",
    "tree_5.root.left.left = Node(10)\n",
    "tree_5.root.left.right = Node(35)\n",
    "tree_5.root.left.right.left = Node(30)\n",
    "tree_5.root.left.left.left = Node(5)\n",
    "tree_5.root.left.left.right = Node(13)\n",
    "\n",
    "tree_5.root.left.left.left.left = Node(2)\n",
    "tree_5.root.left.left.left.left.left = Node(1)\n",
    "tree_5.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "id": "46635090-4e69-4877-9fd1-b701806c4500",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "              25  \n",
      "       /             \\\n",
      "      10              50              \n",
      "   /     \\         /     \\\n",
      "  2       13      35      75      \n",
      " / \\     / \\     / \\     / \\\n",
      "1   5   _   _   30  _   _   _   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_5.rebalance()\n",
    "tree_5.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6557663d-e707-4b3a-89a5-c0a0d4610a25",
   "metadata": {},
   "source": [
    "### C. Challenge 3 --> Smarter Automated Rebalancing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "id": "9b9c127d-4fa1-4cd6-8955-da21931f5c0f",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "    def search(self, target):\n",
    "        if self.data == target:\n",
    "            print(\"Found it!\")\n",
    "            return self\n",
    "        if self.left and self.data > target:\n",
    "            return self.left.search(target)\n",
    "        if self.right and self.data < target:\n",
    "            return self.right.search(target)\n",
    "        print(\"Value not found in tree\")\n",
    "\n",
    "\n",
    "    def traversePreorder(self):\n",
    "        print(self.data, end=\" \")\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traverseInorder()\n",
    "        print(self.data, end=\" \")\n",
    "        if self.right:\n",
    "            self.right.traverseInorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePostorder() \n",
    "        if self.right:\n",
    "            self.right.traversePostorder()\n",
    "        print(self.data, end=\" \")\n",
    "        \n",
    "    def height(self, h=0):\n",
    "        leftHeight = self.left.height(h+1) if self.left else h\n",
    "        rightHeight = self.right.height(h+1) if self.right else h\n",
    "        return max(leftHeight, rightHeight)\n",
    "        \n",
    "    def getNodesAtDepth(self, depth, nodes=[]):\n",
    "        if depth == 0:\n",
    "            nodes.append(self)\n",
    "            return nodes\n",
    "            \n",
    "        if self.left:\n",
    "            self.left.getNodesAtDepth(depth-1, nodes)\n",
    "        else:\n",
    "            nodes.extend([None]*2**(depth-1))\n",
    "            \n",
    "        if self.right:\n",
    "            self.right.getNodesAtDepth(depth-1, nodes)\n",
    "        else:\n",
    "            nodes.extend([None]*2**(depth-1))\n",
    "        return nodes\n",
    "\n",
    "    def findMin(self):\n",
    "        if self.left:\n",
    "            return self.left.findMin()\n",
    "        return self.data\n",
    "    \n",
    "    def delete(self, target):\n",
    "        if self.data == target: \n",
    "            # Do the deletion here\n",
    "            if self.left and self.right:\n",
    "                # RTFM\n",
    "                minValue = self.right.findMin()\n",
    "                self.data = minValue\n",
    "                self.right = self.right.delete(minValue)\n",
    "                return self\n",
    "            else:\n",
    "                return self.left or self.right\n",
    "                \n",
    "        if self.right and target > self.data:\n",
    "            self.right = self.right.delete(target)\n",
    "        if self.left and target < self.data:\n",
    "            self.left = self.left.delete(target)\n",
    "        return self.fixImbalanceIfExists()\n",
    "\n",
    "    def isBalanced(self):\n",
    "        leftHeight = self.left.height() + 1 if self.left else 0\n",
    "        rightHeight = self.right.height() + 1 if self.right else 0\n",
    "        return abs(leftHeight - rightHeight) < 2\n",
    "\n",
    "    def toStr(self):\n",
    "        if not self.isBalanced():\n",
    "            return str(self.data)+'*'\n",
    "        return str(self.data)\n",
    "\n",
    "    def getLeftRightHeightDifference(self):\n",
    "        leftHeight = self.left.height() + 1 if self.left else 0\n",
    "        rightHeight = self.right.height() + 1 if self.right else 0\n",
    "        return leftHeight - rightHeight\n",
    "        \n",
    "    def add(self, data):\n",
    "        if self.data == data:\n",
    "            return \n",
    "        if data < self.data:\n",
    "            if self.left is None:\n",
    "                self.left = Node(data)\n",
    "                self.left = self.left.fixImbalanceIfExists()\n",
    "            else:\n",
    "                self.left.add(data)\n",
    "        else:  # Ensuring BST property\n",
    "            if self.right is None:\n",
    "                self.right = Node(data)\n",
    "            else:\n",
    "                self.right.add(data)\n",
    "                self.right = self.right.fixImbalanceIfExists()\n",
    "        \n",
    "    def fixImbalanceIfExists(self):\n",
    "        if self.getLeftRightHeightDifference() > 1:\n",
    "            # Left Imbalance\n",
    "            if self.left.getLeftRightHeightDifference() > 0:\n",
    "                # Left Left Imbalance\n",
    "                return rotateRight(self)\n",
    "            else:\n",
    "                # Left Right Imbalance\n",
    "                self.left = rotateLeft(self.left)\n",
    "                return rotateRight(self)\n",
    "        elif self.getLeftRightHeightDifference() < -1:\n",
    "            #Right Imbalance\n",
    "            if self.right.getLeftRightHeightDifference() < 0:\n",
    "                # Right Right Imbalance\n",
    "                return rotateLeft(self)\n",
    "            else:\n",
    "                # Right Left Imbalance\n",
    "                self.right = rotateRight(self.right)\n",
    "                return rotateLeft(self)\n",
    "        return self\n",
    "\n",
    "    def rebalance(self):\n",
    "        if self.left:\n",
    "            self.left.rebalance()\n",
    "            self.left = self.left.fixImbalanceIfExists()\n",
    "        if self.right:\n",
    "            self.right.rebalance()\n",
    "            self.right = self.right.fixImbalanceIfExists()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "id": "038a0ad1-1ecf-4cd8-b5c7-1969e1b221b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name=''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "\n",
    "    \n",
    "\n",
    "    def traversePreorder(self):\n",
    "        self.root.traversePreorder()\n",
    "        print()\n",
    "\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "        print()\n",
    "\n",
    "    def traversePostorder(self):\n",
    "        self.root.traversePostorder()\n",
    "        print()\n",
    "\n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "\n",
    "    def getNodesAtDepth(self, depth):\n",
    "        return self.root.getNodesAtDepth(depth)\n",
    "\n",
    "    def _nodeToChar(self, n, spacing):\n",
    "        if n is None:\n",
    "            return '_' + (' ' * spacing)\n",
    "        spacing = spacing - len(n.toStr()) + 1\n",
    "        return n.toStr() + (' ' * spacing)\n",
    "\n",
    "    def print(self, label=''):\n",
    "        print(self.name + ' ' + label)\n",
    "        height = self.root.height()\n",
    "        spacing = 3\n",
    "        width = int((2 ** height - 1) * (spacing + 1) + 1)\n",
    "        offset = int((width - 1) / 2)\n",
    "\n",
    "        for depth in range(0, height + 1):\n",
    "            if depth > 0:\n",
    "                print(' ' * (offset + 1) + (' ' * (spacing + 2)).join(['/' + (' ' * (spacing - 2)) + '\\\\'] * (2 ** (depth - 1))))\n",
    "            row = self.root.getNodesAtDepth(depth, [])\n",
    "            print((' ' * offset) + ''.join([self._nodeToChar(n, spacing) for n in row]))\n",
    "            spacing = offset + 1\n",
    "            offset = max(int(offset / 2) - 1, 0)\n",
    "        print()\n",
    "        \n",
    "    def add(self, data):\n",
    "        self.root.add(data)\n",
    "        self.root = self.root.fixImbalanceIfExists()\n",
    "\n",
    "    def delete(self, target):\n",
    "        self.root = self.root.delete(target)\n",
    "        self.root = self.root.fixImbalanceIfExists()\n",
    "\n",
    "    def rebalance(self):\n",
    "        self.root.rebalance()\n",
    "        self.root = self.root.fixImbalanceIfExists()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "id": "fde1fde2-803f-4cb3-9b3a-670b64acb5d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_6 = Tree(Node(50))\n",
    "tree_6.add(25)\n",
    "tree_6.add(75)\n",
    "tree_6.add(10)\n",
    "tree_6.add(35)\n",
    "tree_6.add(30)\n",
    "tree_6.add(5)\n",
    "tree_6.add(2)\n",
    "tree_6.add(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "id": "f67e464e-7e3f-497c-9b41-c7ca1479437b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "                              25  \n",
      "               /                             \\\n",
      "              10*                             35                              \n",
      "       /             \\                 /             \\\n",
      "      5*              _               30              50              \n",
      "   /     \\         /     \\         /     \\         /     \\\n",
      "  2       _       _       _       _       _       _       75      \n",
      " / \\     / \\     / \\     / \\     / \\     / \\     / \\     / \\\n",
      "1   _   _   _   _   _   _   _   _   _   _   _   _   _   _   _   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_6.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "id": "0d3a8f81-bca2-4f8e-af1a-58a598f794e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "              10  \n",
      "       /             \\\n",
      "      5*              30              \n",
      "   /     \\         /     \\\n",
      "  2       _       25      35      \n",
      " / \\     / \\     / \\     / \\\n",
      "1   _   _   _   _   _   _   _   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_6.delete(50)\n",
    "tree_6.delete(75)\n",
    "tree_6.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f07a906-8561-4278-b0c2-de709f542fc4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}