Python_Data_Structures_Trees_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e42c1aaf-a4b4-499a-a7a1-4924cf399bc0",
   "metadata": {},
   "source": [
    "# LinkedIn Learning\n",
    "# Python Data Structures - Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9600cc9-08d5-467f-bd8c-849a5d38db3e",
   "metadata": {},
   "source": [
    "####  Some Info regarding Trees: - \n",
    "##### 1. One root Node \n",
    "##### 2. Each Node has any number of children.\n",
    "##### 3. Each Node (except root) has one parent.\n",
    "<br>\n",
    "\n",
    "#### Optimal Tree Features: - \n",
    "##### 1. Nodes are associated with some data.\n",
    "##### 2. Rules about how many children a node can have.\n",
    "##### 3. Rules about how many nodes are connected based on their data.\n",
    "<br>\n",
    "\n",
    "#### Binary Search Tree(BST): -\n",
    "##### 1. Each node has, at most can have two children : Left and Right\n",
    "##### 2. Each node has a numeric value associated with it.\n",
    "##### 3. Children to the left must have lesser values than their parents.\n",
    "##### 4. Children to the right must have greater values than their parents.\n",
    "##### 5. No duplicate values.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee4b5e18-49c7-43ed-990d-a4cb0c70aa32",
   "metadata": {},
   "source": [
    "## 1. Navigating Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dde481d-1fea-496d-9fcf-93b32fa365e4",
   "metadata": {},
   "source": [
    "### A. Building a Basic Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "dfe00ad7-fdbc-4317-91c6-58cc2a55cedd",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "81543477-0a9e-4793-b4ca-3cad8c1cd65e",
   "metadata": {},
   "outputs": [],
   "source": [
    "node = Node(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "4f514e47-1d6d-4f9f-9333-c4558d631404",
   "metadata": {},
   "outputs": [],
   "source": [
    "node.left = Node(5)\n",
    "node.right = Node(15)\n",
    "\n",
    "node.left.left = Node(2)\n",
    "node.left.right = Node(6)\n",
    "\n",
    "node.right.left  = Node(13)\n",
    "node.right.right = Node(10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ff1cee0b-5b09-4e82-861b-8dc608e6fd23",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "print(node.right.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "88af8b2e-3eca-42e3-9684-ae3ded275337",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000\n"
     ]
    }
   ],
   "source": [
    "print(node.right.right.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "9bc0da50-132c-476c-ac23-5e61faff9bd1",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name = ''):\n",
    "        self.root = root\n",
    "        self.name = name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a6ef1af8-e5ba-496d-a2a8-9c46d0fa3746",
   "metadata": {},
   "outputs": [],
   "source": [
    "myTree = Tree(node, 'Advait\\'s Tree')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "36639e8c-9f13-4642-b3a0-1c3a58815be1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Advait's Tree\n"
     ]
    }
   ],
   "source": [
    "print(myTree.name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b8ac893c-3105-49da-bf5d-c6cd7e7f576e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "print(myTree.root.left.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "128bfe50-e47b-43aa-ab88-acc177725144",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000\n"
     ]
    }
   ],
   "source": [
    "print(myTree.root.right.right.data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9805160-53a4-4189-a99e-1dddaa7785d7",
   "metadata": {},
   "source": [
    "### B. Searching a Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b9c0bfa4-b392-4b81-a46a-a08ca5b1fc1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\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\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "2a4dcfd9-8409-4e5a-9131-a11b1e75b6c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name = ''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "8481cb2b-09ba-4bf0-abc0-be4cfb745279",
   "metadata": {},
   "outputs": [],
   "source": [
    "node = Node(10)\n",
    "node.left = Node(5)\n",
    "node.right = Node(15)\n",
    "\n",
    "node.left.left = Node(2)\n",
    "node.left.right = Node(6)\n",
    "\n",
    "node.right.left  = Node(13)\n",
    "node.right.right = Node(10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "4cabf186-74ff-4429-bb74-c53def369598",
   "metadata": {},
   "outputs": [],
   "source": [
    "myTree_2 = Tree(node, 'Advait\\'s Tree')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "ad8c0ac7-24ae-4e99-baa6-ed636417e569",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found it!\n",
      "10000\n"
     ]
    }
   ],
   "source": [
    "found = myTree_2.root.search(10000)\n",
    "print(found.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "1a2200bf-9e21-4819-b670-0095d891cda1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found it!\n",
      "10000\n"
     ]
    }
   ],
   "source": [
    "found_1 = myTree_2.search(10000)\n",
    "print(found_1.data)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f70df816-514e-4ef1-868c-4e5b2a56d7e8",
   "metadata": {},
   "source": [
    "### C. Transversing a Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "36efd3df-e6a7-4d1b-88ab-92565009ed4f",
   "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 traversePreorder(self):\n",
    "        print(self.data)\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        print(self.data)\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePreorder() \n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        print(self.data)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "5a882469-2204-46af-b988-51e73b9dec4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name = ''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "    def traversePreorder(self):\n",
    "        self.root.traversePreorder()\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "    def traversePostorder(self):\n",
    "        self.root.traversePostorder()    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "c3721b11-3658-4466-9dc3-3c1e080981a5",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_3 = Tree(Node(50), 'Tree Traversals')\n",
    "tree_3.root.left = Node(25)\n",
    "tree_3.root.right = Node(75)\n",
    "\n",
    "tree_3.root.left.left = Node(10)\n",
    "tree_3.root.left.right = Node(35)\n",
    "\n",
    "tree_3.root.left.right.left = Node(30)\n",
    "tree_3.root.left.right.right = Node(42)\n",
    "\n",
    "tree_3.root.left.left.left = Node(5)\n",
    "tree_3.root.left.left.right = Node(13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "d427e554-b877-4bc3-b22e-5839c41d05e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traverse Pre-Order: -\n",
      "50\n",
      "25\n",
      "10\n",
      "5\n",
      "13\n",
      "35\n",
      "30\n",
      "42\n",
      "75\n"
     ]
    }
   ],
   "source": [
    "print(\"Traverse Pre-Order: -\")\n",
    "tree_3.traversePreorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "187d0498-75fe-43bf-b4e6-2a74320469cb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traverse In-Order: -\n",
      "25\n",
      "10\n",
      "5\n",
      "13\n",
      "35\n",
      "30\n",
      "42\n",
      "50\n",
      "75\n"
     ]
    }
   ],
   "source": [
    "print(\"Traverse In-Order: -\")\n",
    "tree_3.traverseInorder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "edd1abad-b994-405d-b307-8ba892857055",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Traverse Post-Order: -\n",
      "25\n",
      "10\n",
      "5\n",
      "13\n",
      "35\n",
      "30\n",
      "42\n",
      "75\n",
      "50\n"
     ]
    }
   ],
   "source": [
    "print(\"Traverse Post-Order: -\")\n",
    "tree_3.traversePostorder()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0081c7b2-c562-4750-a278-3c6517555506",
   "metadata": {},
   "source": [
    "### D. Getting the Maximum height of a Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "dd84e5f2-de9c-4067-8436-13be46cb3067",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\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",
    "    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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "493460e0-1ef5-4330-9096-60b8e41c08f9",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name = ''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "    def height(self):\n",
    "        return self.root.height()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "d674a1b7-75d9-4586-a8d6-ed78b22c5e72",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_4 = Tree(Node(50), 'A Very Tall Tree')\n",
    "tree_4.root.left = Node(25)\n",
    "tree_4.root.right = Node(75)\n",
    "tree_4.root.left.left = Node(10)\n",
    "tree_4.root.left.right = Node(35)\n",
    "tree_4.root.left.right.left = Node(30)\n",
    "tree_4.root.left.right.right = Node(42)\n",
    "tree_4.root.left.left.left = Node(5)\n",
    "tree_4.root.left.left.right = Node(13)\n",
    "tree_4.root.left.left.left.left = Node(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "8fb8782b-a1df-4a2c-ad1b-2f8673f004e9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "print(tree_4.root.height())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "ad6ee828-1f29-41f4-adff-0dd368094dda",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "tree_5 = Tree(Node(50), 'A very short Tree')\n",
    "print(tree_5.root.height())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "0fb3d725-2315-4c23-a23d-52204d87497c",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_6 = Tree(Node(50), 'A Very Tall Tree')\n",
    "tree_6.root.left = Node(25)\n",
    "tree_6.root.right = Node(75)\n",
    "tree_6.root.left.left = Node(10)\n",
    "tree_6.root.left.right = Node(35)\n",
    "tree_6.root.left.right.left = Node(30)\n",
    "tree_6.root.left.right.right = Node(42)\n",
    "tree_6.root.left.left.left = Node(5)\n",
    "tree_6.root.left.left.right = Node(13)\n",
    "tree_6.root.left.left.left.left = Node(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "90b14a49-1717-4e6c-9429-4466e36fa139",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "print(tree_6.height())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "328d6186-fa38-4d3f-9f73-49cd4b0f07ab",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "tree_7 = Tree(Node(50), 'A very short Tree')\n",
    "print(tree_7.height())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "050cab0d-167e-47af-b39c-e780c8c294e3",
   "metadata": {},
   "source": [
    "### E. Getting all Nodes at a particular height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "ccfb176b-e1df-4cbd-971a-cc5c4f40203d",
   "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 traversePreorder(self):\n",
    "        print(self.data)\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "        \n",
    "    def traverseInorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePreorder()\n",
    "        print(self.data)\n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        \n",
    "    def traversePostorder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePreorder() \n",
    "        if self.right:\n",
    "            self.right.traversePreorder()\n",
    "        print(self.data)\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.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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "edfede6a-94a4-4caf-9645-ecb641920c37",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name = ''):\n",
    "        self.root = root\n",
    "        self.name = name\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "    def traversePreorder(self):\n",
    "        self.root.traversePreorder()\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "    def traversePostorder(self):\n",
    "        self.root.traversePostorder()    \n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "    def getNodesAtDepth(self, depth):\n",
    "        return self.root.getNodesAtDepth(depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "24c19496-4267-49b6-96ae-37773d19206a",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_8 = Tree(Node(50), 'Get all nodes at depth')\n",
    "tree_8.root.left = Node(25)\n",
    "tree_8.root.right = Node(75)\n",
    "tree_8.root.left.left = Node(13)\n",
    "tree_8.root.left.right = Node(35)\n",
    "tree_8.root.left.right.right = Node(37)\n",
    "tree_8.root.right.left = Node(55)\n",
    "tree_8.root.right.right = Node(103)\n",
    "tree_8.root.left.left.left = Node(2)\n",
    "tree_8.root.left.left.right = Node(20)\n",
    "tree_8.root.right.left = Node(55)\n",
    "tree_8.root.right.right.right = Node(256)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "b0fd62b1-7b68-4f48-9a06-e074a1435b07",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[13, 35, 55, 103]\n"
     ]
    }
   ],
   "source": [
    "print(tree_8.getNodesAtDepth(2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "a28fa68a-95a2-427c-8a64-bc69f9c1f575",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[13, 35, 55, 103, 2, 20, 37, 256]\n"
     ]
    }
   ],
   "source": [
    "print(tree_8.getNodesAtDepth(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "430bbc53-92d5-4ce8-941e-a738834a839c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[13, 35, 55, 103, 2, 20, 37, 256]\n"
     ]
    }
   ],
   "source": [
    "print(tree_8.getNodesAtDepth(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "44d7f5bd-56fe-42bd-ae7d-79745d72cbf4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[13, 35, 55, 103, 2, 20, 37, 256, 25, 75]\n"
     ]
    }
   ],
   "source": [
    "print(tree_8.getNodesAtDepth(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "ddf655f6-3d88-4071-af8b-7612a8fda9cd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[13, 35, 55, 103, 2, 20, 37, 256, 25, 75]\n"
     ]
    }
   ],
   "source": [
    "print(tree_8.getNodesAtDepth(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "095fa916-d56b-4ae9-a76b-370506c3bfc5",
   "metadata": {},
   "source": [
    "### F. Challenge _ 1 --> Printing a Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "79b3cce9-991f-4b58-9b86-077be5d17144",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Tree:\n",
    "    def __init__(self, root, name = ''):\n",
    "        self.root = root\n",
    "        self.name = name \n",
    "\n",
    "    def _nodeToChar(self, n, spacing):\n",
    "        if n is None:\n",
    "            return '_'+(' '*spacing)\n",
    "        spacing = spacing - len(str(n)) + 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",
    "        # Root Offset\n",
    "        offset = int((width - 1)/2)\n",
    "        for depth in range(0, height + 1):\n",
    "            if depth > 0:\n",
    "                # Print Directional lines\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 = int(offset/2) - 1\n",
    "        print('')\n",
    "    def search(self, target):\n",
    "        return self.root.search(target)\n",
    "    def traversePreorder(self):\n",
    "        self.root.traversePreorder()\n",
    "    def traverseInorder(self):\n",
    "        self.root.traverseInorder()\n",
    "    def traversePostorder(self):\n",
    "        self.root.traversePostorder()    \n",
    "    def height(self):\n",
    "        return self.root.height()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "8e326c3d-7271-40a2-8a47-82be1eef2713",
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_9 = Tree(Node(50), 'Advait\\'s Cool Tree')\n",
    "tree_9.root.left = Node(25)\n",
    "tree_9.root.right = Node(75)\n",
    "tree_9.root.left.left = Node(13)\n",
    "tree_9.root.left.right = Node(35)\n",
    "tree_9.root.left.right.right = Node(37)\n",
    "tree_9.root.right.left = Node(55)\n",
    "tree_9.root.right.right = Node(103)\n",
    "tree_9.root.left.left.left = Node(2)\n",
    "tree_9.root.left.left.right = Node(20)\n",
    "tree_9.root.right.left = Node(55)\n",
    "tree_9.root.right.right.right = Node(256)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "a4ded935-33f2-4ae8-8056-527ebae9d36e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Advait's Cool Tree\n",
      "              50  \n",
      "       /             \\\n",
      "      25              75              \n",
      "   /     \\         /     \\\n",
      "  13      35      55      103     \n",
      " / \\     / \\     / \\     / \\\n",
      "2   20  37  256 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "tree_9.print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "800f8841-bd72-45d1-b991-b0ea02e38ed4",
   "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
}