Day 21 -  Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "72b3f15c",
   "metadata": {},
   "source": [
    "# Day 21: Trees\n",
    "    \n",
    "- ### Binary Trees\n",
    "- ### Binary Search Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b35f8979",
   "metadata": {},
   "outputs": [],
   "source": [
    "# !ls images/"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d527fbb",
   "metadata": {},
   "source": [
    "<img src=\"images/tree.png\" height=400px width=400px>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a455737b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "650fd6e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Defaulting to user installation because normal site-packages is not writeable\n",
      "Requirement already satisfied: graphviz in /home/dell/.local/lib/python3.8/site-packages (0.20.1)\n"
     ]
    }
   ],
   "source": [
    "!pip3 install graphviz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ce2c9e5e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from graphviz import Digraph\n",
    "\n",
    "def visualize_tree(tree):\n",
    "    if tree is None: return \"Nothing in the tree\"\n",
    "    def add_nodes_edges(tree, dot=None):\n",
    "        \n",
    "        # create a digraph object\n",
    "        if dot is None:\n",
    "            dot = Digraph()\n",
    "            dot.attr('node', shape=\"circle\")\n",
    "            dot.node(name=str(tree), label=str(tree.val))\n",
    "            \n",
    "        for child in [tree.left, tree.right]:\n",
    "            if child is not None:\n",
    "                if child == tree.left: dot.attr(\"node\", shape=\"circle\", style=\"filled\")\n",
    "                if child == tree.right: dot.attr(\"node\", shape=\"doublecircle\", style=\"filled\", color=\"red\")\n",
    "                dot.node(name=str(child), label= str(child.val))\n",
    "                dot.edge(str(tree), str(child))\n",
    "                dot = add_nodes_edges(child, dot=dot)\n",
    "                \n",
    "        return dot\n",
    "    dot = add_nodes_edges(tree)\n",
    "    display(dot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e4ef669e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pre order Traversal: 1 2 4 4 3 \n",
      "In order Traversal: 4 4 2 1 3 \n",
      "Post order Traversal: 4 4 2 3 1 "
     ]
    }
   ],
   "source": [
    "# Binary Tree in Python\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, key):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = key\n",
    "\n",
    "    # Traverse preorder\n",
    "    def traversePreOrder(self):\n",
    "        print(self.val, end=' ')\n",
    "        if self.left:\n",
    "            self.left.traversePreOrder()\n",
    "        if self.right:\n",
    "            self.right.traversePreOrder()\n",
    "\n",
    "    # Traverse inorder\n",
    "    def traverseInOrder(self):\n",
    "        if self.left:\n",
    "            self.left.traverseInOrder()\n",
    "        print(self.val, end=' ')\n",
    "        if self.right:\n",
    "            self.right.traverseInOrder()\n",
    "\n",
    "    # Traverse postorder\n",
    "    def traversePostOrder(self):\n",
    "        if self.left:\n",
    "            self.left.traversePostOrder()\n",
    "        if self.right:\n",
    "            self.right.traversePostOrder()\n",
    "        print(self.val, end=' ')\n",
    "\n",
    "\n",
    "root = Node(1)\n",
    "\n",
    "root.left = Node(2)\n",
    "root.right = Node(3)\n",
    "\n",
    "root.left.left = Node(4)\n",
    "root.left.left.right = Node(4)\n",
    "\n",
    "\n",
    "print(\"Pre order Traversal: \", end=\"\")\n",
    "root.traversePreOrder()\n",
    "print(\"\\nIn order Traversal: \", end=\"\")\n",
    "root.traverseInOrder()\n",
    "print(\"\\nPost order Traversal: \", end=\"\")\n",
    "root.traversePostOrder()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d63827e5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.43.0 (0)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"110pt\" height=\"276pt\"\n",
       " viewBox=\"0.00 0.00 110.00 276.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 272)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-272 106,-272 106,4 -4,4\"/>\n",
       "<!-- __main__.Node object at 0x7fc66464d3d0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>__main__.Node object at 0x7fc66464d3d0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"51\" cy=\"-250\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"51\" y=\"-246.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- __main__.Node object at 0x7fc66464d430 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>__main__.Node object at 0x7fc66464d430</title>\n",
       "<ellipse fill=\"lightgrey\" stroke=\"black\" cx=\"22\" cy=\"-174\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"22\" y=\"-170.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- __main__.Node object at 0x7fc66464d3d0&#45;&gt;__main__.Node object at 0x7fc66464d430 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>__main__.Node object at 0x7fc66464d3d0&#45;&gt;__main__.Node object at 0x7fc66464d430</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M44.71,-232.94C40.98,-223.44 36.18,-211.19 31.95,-200.4\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"35.19,-199.06 28.28,-191.03 28.67,-201.61 35.19,-199.06\"/>\n",
       "</g>\n",
       "<!-- __main__.Node object at 0x7fc66464d400 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>__main__.Node object at 0x7fc66464d400</title>\n",
       "<ellipse fill=\"red\" stroke=\"red\" cx=\"80\" cy=\"-174\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"red\" cx=\"80\" cy=\"-174\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"80\" y=\"-170.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- __main__.Node object at 0x7fc66464d3d0&#45;&gt;__main__.Node object at 0x7fc66464d400 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>__main__.Node object at 0x7fc66464d3d0&#45;&gt;__main__.Node object at 0x7fc66464d400</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M57.29,-232.94C60.59,-224.53 64.73,-213.95 68.58,-204.15\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"71.88,-205.3 72.27,-194.72 65.37,-202.75 71.88,-205.3\"/>\n",
       "</g>\n",
       "<!-- __main__.Node object at 0x7fc66464d460 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>__main__.Node object at 0x7fc66464d460</title>\n",
       "<ellipse fill=\"lightgrey\" stroke=\"black\" cx=\"22\" cy=\"-98\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"22\" y=\"-94.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- __main__.Node object at 0x7fc66464d430&#45;&gt;__main__.Node object at 0x7fc66464d460 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>__main__.Node object at 0x7fc66464d430&#45;&gt;__main__.Node object at 0x7fc66464d460</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M22,-155.84C22,-147.06 22,-136.16 22,-126.27\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"25.5,-126.07 22,-116.07 18.5,-126.07 25.5,-126.07\"/>\n",
       "</g>\n",
       "<!-- __main__.Node object at 0x7fc66464d490 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>__main__.Node object at 0x7fc66464d490</title>\n",
       "<ellipse fill=\"red\" stroke=\"red\" cx=\"22\" cy=\"-22\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"red\" cx=\"22\" cy=\"-22\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"22\" y=\"-18.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- __main__.Node object at 0x7fc66464d460&#45;&gt;__main__.Node object at 0x7fc66464d490 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>__main__.Node object at 0x7fc66464d460&#45;&gt;__main__.Node object at 0x7fc66464d490</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M22,-79.84C22,-72.16 22,-62.88 22,-54.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"25.5,-54.03 22,-44.03 18.5,-54.03 25.5,-54.03\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.graphs.Digraph at 0x7fc664701250>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "visualize_tree(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cb7f3965",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}