Tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "587a35d7-dadf-48e6-9c28-49cb2d284504",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Tree\n",
    "\n",
    "https://docs.google.com/spreadsheets/d/1YiFjKh5ceGkVNNbu_jrxltBlbry3s0jA80HAm8HwkrY/edit#gid=1993476499\n",
    "* Tree is a non-linear data structure\n",
    "* It stores the data in the form of Heirarchy\n",
    "* Root Node (degree = 0 )\n",
    "* Leaf Node\n",
    "* Parent Node\n",
    "* It is recursive in nature\n",
    "* It contains sub-trees\n",
    "* descendants\n",
    "* ancestors\n",
    "* degree\n",
    "* internal nodes\n",
    "\n",
    "**Problems**\n",
    "\n",
    "Make the below links workable??\n",
    "[Click Me](https://nbviewer.org/github/ChandrashekharRobbi/GFG-DSA/blob/main/Tree.ipynb?flush_cache=true)\n",
    "\n",
    "1. [Binary Search Tree](#Binary-Search-Tree)\n",
    "7. [Tree Traversal](#Tree-Traversal)\n",
    "7. [Inorder Traversal](#Inorder-Traversal)\n",
    "7. [preorder Traversal](#preorder-Traversal)\n",
    "7. [PostOrder Traversal](#PostOrder-Traversal)\n",
    "7. [Height of Binary Tree](#Height-of-Binary-Tree)\n",
    "1. [Print the nodes at distance K](#Print-the-nodes-at-distance-K)\n",
    "1. [Level Order Traversal](#Level-Order-Traversal)\n",
    "1. [Size of Binary Tree](#Size-of-Binary-Tree)\n",
    "1. [Maximum in Binary Tree](#Maximum-in-Binary-Tree)\n",
    "1. [Determine if Two Trees are identical](#Determine-if-Two-Trees-are-identical)\n",
    "1. [Check for Balanced Tree](#Check-for-Balanced-Tree)\n",
    "1. [Level Order Traversal print in same way which is traversed ](#Level-Order-Traversal-print-in-same-way-which-is-traversed)\n",
    "1. [Vertical Level Traversal](#Vertical-Level-Traversal)\n",
    "1. [Bottom View of Binary Tree](#Bottom-View-of-Binary-Tree)\n",
    "1. [Maximum Width of a Binary Tree](#Maximum-Width-of-a-Binary-Tree)\n",
    "1. [Convert Tree to Doubly Linked List](#Convert-Tree-to-Doubly-Linked-List)\n",
    "1. [Construct Tree From Inorder and preorder](#Construct-Tree-From-Inorder-and-preorder)\n",
    "1. [Tree Traversal in Spiral Form](#Tree-Traversal-in-Spiral-Form)\n",
    "1. [Diameter of a Binary Tree](#Diameter-of-a-Binary-Tree)\n",
    "1. [Lowest Common Ancestor (LCA) of Binary Tree](#Lowest-Common-Ancestor-(LCA)-of-Binary-Tree)\n",
    "1. [Count Nodes in Binary Tree](#Count-Nodes-in-Binary-Tree)\n",
    "1. [Serialize and Desrialize](#Serialize-and-Desrialize)\n",
    "1. [Iterative Inorder Traversal](#Iterative-Inorder-Traversal)\n",
    "1. [Iterative PreOrder](#Iterative-PreOrder)\n",
    "1. [Lowest Common Ancestor (LCA) of Binary Tree](#Lowest-Common-Ancestor-(LCA)-of-Binary-Tree)\n",
    "1. [Lowest Common Ancestor Of Deepest Leafes](#Lowest-Common-Ancestor-Of-Deepest-Leafes)\n",
    "1. [Count Nodes in Binary Tree](#Count-Nodes-in-Binary-Tree)\n",
    "1. [Serialize and Desrialize](#Serialize-and-Desrialize)\n",
    "1. [Left View of Binary Tree](#Left-View-of-Binary-Tree)\n",
    "1. [Left View Traversal using HashMap](#Left-View-Traversal-using-HashMap)\n",
    "1. [Right View By using HashMap](#Right-View-By-using-HashMap)\n",
    "1. [Vertical Width of a Binary Tree](#Vertical-Width-of-a-Binary-Tree)\n",
    "1. [Create Tree](#Create-Tree)\n",
    "1. [Print Value in Tree](#Print-Value-in-Tree)\n",
    "1. [Level Order Traversal Seperate LIne](#Level-Order-Traversal-Seperate-LIne)\n",
    "1. [Flatten Binary Tree](#Flatten-Binary-Tree)\n",
    "1. [Burn a Binary Tree <img src=\"https://em-content.zobj.net/source/animated-noto-color-emoji/356/fire_1f525.gif\" width=20 height=20/>](#Burn-a-Binary-Tree-)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "bb1c57ed",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Note that after executing new function your next cell will automatically converted to markdown cell :)\n"
     ]
    }
   ],
   "source": [
    "%run imp_personal.py\n",
    "z = MyFunction()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9444519",
   "metadata": {
    "tags": []
   },
   "source": [
    "\n",
    "<img src=\"https://miro.medium.com/max/1400/1*YMqkwxqb1KhEAkwymNFnbA.png\" align=\"left\" width=\"700px\"/>\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b71bab8b",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Binary Search Tree\n",
    "\n",
    "* At most it contains two childrens or we can say atmost it can have 2 degree at any node\n",
    "* If root is None then binary tree is empty"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be9c000a",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Using Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "73f7f192",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,k):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.key = k"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2566ef7b",
   "metadata": {},
   "source": [
    "<img src=\"https://static.javatpoint.com/ds/images/binary-tree.png\" align=\"right\" width=\"200px\" height=\"100px\"/>\n",
    "\n",
    "```python\n",
    "bt_root = Node(1)\n",
    "bt_root.left = Node(2)\n",
    "bt_root.right = Node(3)\n",
    "bt_root.left.left = Node(5)\n",
    "bt_root.left.right = Node(6)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f8a113c",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Tree Traversal\n",
    "<img src=\"https://media.geeksforgeeks.org/wp-content/cdn-uploads/Preorder-from-Inorder-and-Postorder-traversals.jpg\"/>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "1. Breadth First (Level Order)\n",
    "2. Depth First\n",
    "    * Inorder (Left Root Right)\n",
    "    * Preorder (Root Left Right)\n",
    "    * Postorder (Left Right Root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b6a587f",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Inorder Traversal\n",
    "\n",
    "Left , Root , Right"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d18e334d",
   "metadata": {},
   "source": [
    "\n",
    "<img src=\"img/Tree-binary-graph-for-inorder.png\" width=\"500px\" height=\"200px\" align=\"right\"/>\n",
    "\n",
    "```python\n",
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.right.left = Node(40)\n",
    "root.right.right = Node(50)\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "249c9ddb",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.right.left = Node(40)\n",
    "root.right.right = Node(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "656d4bd9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def inorder(root):\n",
    "    if root != None:\n",
    "        inorder(root.left)\n",
    "        print(root.key)\n",
    "        inorder(root.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "330e2c2c",
   "metadata": {},
   "source": [
    "<img src=\"img/recursive-inorder-flow.png\" width=\"500px\" height=\"200px\" align=\"right\"/>\n",
    "\n",
    "```python\n",
    "def inorder(root):\n",
    "    if root != None:\n",
    "        inorder(root.left)\n",
    "        print(root.key)\n",
    "        inorder(root.right)\n",
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.right.left = Node(40)\n",
    "root.right.right = Node(50)\n",
    "\n",
    "inorder(root)\n",
    "```\n",
    "**OUTPUT**\n",
    "\n",
    "```\n",
    "20\n",
    "10\n",
    "40\n",
    "30\n",
    "50\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "b201f6ca",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "10\n",
      "40\n",
      "30\n",
      "50\n"
     ]
    }
   ],
   "source": [
    "inorder(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dc10282",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### preorder Traversal\n",
    "Root Left Right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "17d48b8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def preorder(root):\n",
    "    if root != None:\n",
    "        print(root.key)\n",
    "        preorder(root.left)\n",
    "        preorder(root.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a49f9ff",
   "metadata": {},
   "source": [
    "<img src=\"img/recursive-preorder-flow.png\" width=\"500px\" height=\"200px\" align=\"right\"/>\n",
    "\n",
    "```python\n",
    "def preorder(root):\n",
    "    if root != None:\n",
    "        print(root.key)\n",
    "        preorder(root.left)\n",
    "        preorder(root.right)\n",
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.right.left = Node(40)\n",
    "root.right.right = Node(50)\n",
    "\n",
    "preorder(root)\n",
    "```\n",
    "**OUTPUT**\n",
    "\n",
    "```\n",
    "10\n",
    "20\n",
    "30\n",
    "40\n",
    "50\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "8ca44b86",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "20\n",
      "30\n",
      "40\n",
      "50\n"
     ]
    }
   ],
   "source": [
    "preorder(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20997bc6",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Postorder Traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "35a1b07d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def postorder(root):\n",
    "    if root != None:\n",
    "        postorder(root.left)\n",
    "        postorder(root.right)\n",
    "        print(root.key)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7483cb53",
   "metadata": {},
   "source": [
    "<img src=\"img/recursive-postorder-flow.png\" width=\"500px\" height=\"200px\" align=\"right\"/>\n",
    "\n",
    "```python\n",
    "def postorder(root):\n",
    "    if root != None:\n",
    "        postorder(root.left)\n",
    "        postorder(root.right)\n",
    "        print(root.key)\n",
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.right.left = Node(40)\n",
    "root.right.right = Node(50)\n",
    "\n",
    "postorder(root)\n",
    "```\n",
    "**OUTPUT**\n",
    "\n",
    "```\n",
    "20\n",
    "40\n",
    "50\n",
    "30\n",
    "10\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "fc36d76e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "40\n",
      "50\n",
      "30\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "postorder(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "612f1ef6",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Height of Binary Tree\n",
    "\n",
    "It can be solved using two convention\n",
    "1. No of nodes from root node to leaf node\n",
    "2. maximum number of edges from root to leaf node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "9b1d68d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def height(root):\n",
    "    if root == None:\n",
    "        return 0\n",
    "    else:\n",
    "        lh = height(root.left) # left height\n",
    "        rh = height(root.right) # right height\n",
    "        return max(lh,rh) + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3998417",
   "metadata": {},
   "source": [
    "<img src=\"img/recursive-height-flow.png\" width=\"500px\" height=\"200px\" align=\"right\"/>\n",
    "\n",
    "```python\n",
    "def height(root):\n",
    "    if root == None:\n",
    "        return 0\n",
    "    else:\n",
    "        lh = height(root.left) # left height\n",
    "        rh = height(root.right) # right height\n",
    "        return max(lh,rh) + 1\n",
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.right.left = Node(40)\n",
    "root.right.right = Node(50)\n",
    "\n",
    "height(root)\n",
    "```\n",
    "**OUTPUT**\n",
    "\n",
    "```\n",
    "3\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "a8d7df7b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "height(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58b2312b-62d5-4ac8-9d5e-35d595241535",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Print the nodes at distance K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "1b748d86-186d-4201-9811-0e7fb242eb18",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance_till_k(root, K):\n",
    "    if root is None:\n",
    "        return\n",
    "    if K == 0:\n",
    "        print(root.key, end=\" \")\n",
    "    else:\n",
    "        distance_till_k(root.left, K - 1)\n",
    "        distance_till_k(root.right, K - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9030f4e-7526-47e1-8059-379f9f8fca44",
   "metadata": {},
   "source": [
    "<img src=\"img/Tree-binary-graph-for-inorder.png\" width=\"600px\"  />"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b9c7191-a3d0-40db-9ca8-d61564b3bfbf",
   "metadata": {},
   "source": [
    "**Time Complexity** :- O(n)\n",
    "\n",
    "\n",
    "**Space Complexity** :- O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "27a90baf-80eb-46d0-af8d-a4a84ba8a917",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40 50 "
     ]
    }
   ],
   "source": [
    "distance_till_k(root,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de7ef565-c93d-45d7-8734-a1f01c79ba00",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Level Order Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a096ce24-214e-4a4b-871d-c0a5e9e58e50",
   "metadata": {},
   "source": [
    "##### naive approach\n",
    "\n",
    "It takes `O(n + nh)` Time Complexity "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "468889fb-0732-43ce-9099-0fc94e1ac14c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Level_order_traversal_naive(root):\n",
    "    h = height(root)\n",
    "    for k in range(h):\n",
    "        distance_till_k(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "e1bdfdcb-6352-4db3-8201-36ef0464c0af",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 20 30 40 50 "
     ]
    }
   ],
   "source": [
    "Level_order_traversal_naive(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bee554d-3ece-4c4d-95be-eb09d634918e",
   "metadata": {},
   "source": [
    "##### Let's find the solution which takes Linear time\n",
    "\n",
    "We are going to use `queue` data structure and iterative solution \n",
    "\n",
    "Because as recursive we are unable to shift to next node instantly we have to look for entire subtree and then we can switch which will be required unnecessary call stack"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd7961e8-fb01-4127-8576-a8359d85beb4",
   "metadata": {},
   "source": [
    "<img src=\"img/tree-binary-graph.png\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "4abac0be-7a07-4b97-98b9-0411bc13d2b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.left.left = Node(40)\n",
    "root.left.right = Node(50)\n",
    "root.right.right = Node(70)\n",
    "root.right.left = Node(60)\n",
    "root.left.right.left = Node(80)\n",
    "root.right.left.right = Node(90)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d394d7ea-00c4-4aaa-bdbd-0936e5ff701f",
   "metadata": {},
   "source": [
    "**Time Complexity**\n",
    "\n",
    "O(n)\n",
    "\n",
    "**Space Complexity**\n",
    "\n",
    "O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "d8b8f782-9392-4d75-9d67-ca4c56774714",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "def Level_order_traversal(root):\n",
    "    if root == None:\n",
    "        return\n",
    "    q = deque()\n",
    "    q.append(root)\n",
    "    while len(q) > 0:\n",
    "        node = q.popleft()\n",
    "        print(node.key)\n",
    "        \n",
    "        if node.left != None:\n",
    "            q.append(node.left)\n",
    "        if node.right != None:\n",
    "            q.append(node.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "73c5e8f0-7bf6-4a1b-b2b4-fe9945b75e44",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "20\n",
      "30\n",
      "40\n",
      "50\n",
      "60\n",
      "70\n",
      "80\n",
      "90\n"
     ]
    }
   ],
   "source": [
    "Level_order_traversal(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ebc65a12-39b8-47fd-a8b0-52e2d7aaadd8",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Size of Binary Tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "ebb22e3c-e07c-441d-9e05-9d6a53d2a342",
   "metadata": {},
   "outputs": [],
   "source": [
    "def size_binary_tree(root):\n",
    "    if root == None:\n",
    "        return 0\n",
    "    else:\n",
    "        ld = size_binary_tree(root.left)\n",
    "        rd = size_binary_tree(root.right)\n",
    "        return ld + rd + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "70d840de-c4db-41fa-9ba0-f102a95ca51a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "size_binary_tree(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79523a56-c103-45b3-91a1-baf89f09ee9c",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Maximum in Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "a007630e-5c4b-44cf-98f5-4d3f8ddb31fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def maxBinaryTree(root):\n",
    "    if root == None:\n",
    "        return -math.inf\n",
    "    else:\n",
    "        leftMax = maxBinaryTree(root.left)\n",
    "        rightMax = maxBinaryTree(root.right)\n",
    "        return max(leftMax, rightMax, root.key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "8eccd59c-3da4-49fc-84e3-b48656622686",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "90"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maxBinaryTree(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ffec509",
   "metadata": {},
   "source": [
    "#### Determine if Two Trees are identical"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "933f42fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isIdentical(root1, root2):\n",
    "    if root1 == None and root2 == None:\n",
    "        return True\n",
    "    if root1 != None and root2 != None:\n",
    "        return ((root1.data == root2.data) and \n",
    "                isIdentical(root1.left, root2.left) and \n",
    "                isIdentical(root1.right, root2.right))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35951435",
   "metadata": {},
   "source": [
    "#### Check for Balanced Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "60042d51",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBalanced1(root):\n",
    "    if root == None:\n",
    "        return True\n",
    "    lh = isBalanced(root.left)\n",
    "    \n",
    "    if lh == 0:\n",
    "        return 0\n",
    "    \n",
    "    rh = isBalanced(root.right)\n",
    "    \n",
    "    if rh == 0:\n",
    "        return 0\n",
    "    \n",
    "    if abs(lh - rh) > 1:\n",
    "        return 0\n",
    "    else:\n",
    "        return max(lh, rh) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "8cb92438",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBalanced2(root):\n",
    "    if root == None:\n",
    "        return True\n",
    "    lh = height(root.left)\n",
    "    rh = height(root.right)\n",
    "    return abs(lh - rh) <= 1 and \\\n",
    "            isBalanced2(root.left) and \\\n",
    "            isBalanced2(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "27a22b6a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isBalanced2(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "806dc4a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBalanced3(root):\n",
    "    if root == None:\n",
    "        return 0\n",
    "    lh = isBalanced3(root.left)\n",
    "    if lh == -1:\n",
    "        return -1\n",
    "    rh = isBalanced3(root.right)\n",
    "    if rh == -1:\n",
    "        return -1 \n",
    "    if abs(rh - lh) > 1:\n",
    "        return -1\n",
    "    return max(lh, rh) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "7e6d203e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBalancedMain(root):\n",
    "    if isBalanced3(root) == -1:\n",
    "        return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "f8c2883f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isBalancedMain(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1285344b",
   "metadata": {},
   "source": [
    "## Level Order Traversal print in same way which is traversed "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "a625599a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "40\n",
      "20\n",
      "80\n",
      "50\n",
      "10\n",
      "60\n",
      "90\n",
      "30\n",
      "70\n"
     ]
    }
   ],
   "source": [
    "inorder(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "46e74b0c",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "def levelOrderTraversal1(root):\n",
    "    # if root is None\n",
    "    if root is None:\n",
    "        return\n",
    "    # create queue for storing the values\n",
    "    q = deque()\n",
    "    # append the first root node\n",
    "    q.append(root)\n",
    "    # also append the None so that we will know that one step is completed\n",
    "    q.append(None)\n",
    "    while len(q) > 1:\n",
    "        # pop the left most value and store it\n",
    "        curr = q.popleft()\n",
    "        # if curr is None then that means we have completed the step\n",
    "        if curr == None:\n",
    "            print()\n",
    "            # append the None to already inserted node values\n",
    "            q.append(None)\n",
    "            continue\n",
    "        print(curr.key, end= \" \")\n",
    "        # If current left node is not null, then Append\n",
    "        if curr.left != None:\n",
    "            q.append(curr.left)\n",
    "        # If current right node is not null, then append.\n",
    "        if curr.right != None:\n",
    "            q.append(curr.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "456d6f3c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 \n",
      "20 30 \n",
      "40 50 60 70 \n",
      "80 90 "
     ]
    }
   ],
   "source": [
    "levelOrderTraversal1(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "2c10f9a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def levelOrderTraversal2(root):\n",
    "    if root == None:\n",
    "        return\n",
    "    q = deque()\n",
    "    q.append(root)\n",
    "    while len(q) > 0:\n",
    "        count = len(q)\n",
    "        for i in range(count):\n",
    "            curr = q.popleft()\n",
    "            print(curr.key, end= \" \")\n",
    "            if curr.left != None:\n",
    "                q.append(curr.left)\n",
    "            if curr.right != None:\n",
    "                q.append(curr.right)\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "8ba431bf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 \n",
      "20 30 \n",
      "40 50 60 70 \n",
      "80 90 \n"
     ]
    }
   ],
   "source": [
    "levelOrderTraversal2(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36bdce77",
   "metadata": {},
   "source": [
    "## Vertical Level Traversal\n",
    "\n",
    "<img src=\"https://media.geeksforgeeks.org/wp-content/cdn-uploads/print-binary-tree-in-vertical-order.png\" align=\"right\"/>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "```py\n",
    "root = Node(1)\n",
    "root.left = Node(2)\n",
    "root.right = Node(3)\n",
    "root.left.left = Node(4)\n",
    "root.left.right = Node(5)\n",
    "root.right.left = Node(6)\n",
    "root.right.right = Node(7)\n",
    "root.right.left.right = Node(8)\n",
    "root.right.right.right = Node(9)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "681e7d8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = Node(1)\n",
    "root.left = Node(2)\n",
    "root.right = Node(3)\n",
    "root.left.left = Node(4)\n",
    "root.left.right = Node(5)\n",
    "root.right.left = Node(6)\n",
    "root.right.right = Node(7)\n",
    "root.right.left.right = Node(8)\n",
    "root.right.right.right = Node(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "ccadd433",
   "metadata": {},
   "outputs": [],
   "source": [
    "# first find the Minimum and Maximum Horizontal Distance\n",
    "def findMinMax(root, mini, maxi, hd):\n",
    "    if root is None:\n",
    "        return\n",
    "    \n",
    "    # update min and max values\n",
    "    if hd < mini[0]:\n",
    "        mini[0] = hd\n",
    "    elif hd > maxi[0]:\n",
    "        maxi[0] = hd\n",
    "    \n",
    "    # call recursively\n",
    "    findMinMax(root.left, mini, maxi, hd - 1) # when we go left then we decrement by -1\n",
    "    findMinMax(root.right, mini, maxi, hd + 1)# when we go right then we increment by +1\n",
    "\n",
    "# make the utility function to print the vertical line\n",
    "def printVerticalLine(root, line_no, hd):\n",
    "    if root is None:\n",
    "        return\n",
    "    if hd == line_no:\n",
    "        print(root.key, end=\" \")\n",
    "    # make recursive call\n",
    "    printVerticalLine(root.left, line_no, hd-1)\n",
    "    printVerticalLine(root.right, line_no, hd+1)\n",
    "    \n",
    "# make the utility function to print in Vertical Order\n",
    "def printVerticalOrder(root):\n",
    "    mini = [0]\n",
    "    maxi = [0]\n",
    "    \n",
    "    findMinMax(root, mini, maxi, 0)# hd is 0 as we are in the root\n",
    "    \n",
    "    for line_no in range(mini[0], maxi[0] + 1):\n",
    "        printVerticalLine(root, line_no, 0)\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "8eacd6aa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 \n",
      "2 \n",
      "1 5 6 \n",
      "3 8 \n",
      "7 \n",
      "9 \n"
     ]
    }
   ],
   "source": [
    "printVerticalOrder(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f647e384",
   "metadata": {},
   "source": [
    "## Bottom View of Binary Tree\n",
    "\n",
    "    Input:                20\n",
    "                        /     \\\n",
    "                      8         22\n",
    "                   /      \\         \\\n",
    "                 5         3        25\n",
    "                       /    \\      \n",
    "                     10       14\n",
    "\n",
    "    Output: 5, 10, 3, 14, 25.\n",
    "\n",
    "    Input:                20\n",
    "                        /     \\\n",
    "                      8         22\n",
    "                   /    \\     /     \\\n",
    "                  5      3    4      25\n",
    "                      /    \\      \n",
    "                   10       14\n",
    "\n",
    "\n",
    "    Output: 5 10 4 14 25. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "7e2f56cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "root2 = Node(20)\n",
    "root2.left = Node(8)\n",
    "root2.right = Node(22)\n",
    "root2.left.left = Node(5)\n",
    "root2.left.right = Node(3)\n",
    "root2.right.right = Node(25)\n",
    "root2.left.right.left = Node(10)\n",
    "root2.left.right.right = Node(14)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "6f3d1c10",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "31fa2881",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bottomView(root):\n",
    "    mp = {}\n",
    "    q = deque() # for storing nodes\n",
    "    q1 = deque() # for storing the values\n",
    "    \n",
    "    q.append(root2)\n",
    "    q1.append(0)\n",
    "    while len(q)>0:\n",
    "        curr = q.popleft()\n",
    "        hd = q1.popleft()\n",
    "        # overwrite the values if exists\n",
    "        mp[hd] = curr.key\n",
    "        if curr.right != None:\n",
    "            q.append(curr.right)\n",
    "            q1.append(hd + 1)\n",
    "        if curr.left != None:\n",
    "            q.append(curr.left)\n",
    "            q1.append(hd - 1)\n",
    "            \n",
    "    for i in sorted(mp.keys()):\n",
    "        print(mp[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "c69dcbfc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "10\n",
      "3\n",
      "14\n",
      "25\n"
     ]
    }
   ],
   "source": [
    "bottomView(root2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "457e8888",
   "metadata": {},
   "source": [
    "## Maximum Width of a Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "cfb894e4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Line by Line Traversal\n",
    "def getMaxWidth(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    q = deque()\n",
    "    q.append(root)\n",
    "    res = 0\n",
    "    while len(q) > 0:\n",
    "        count = len(q)\n",
    "        for _ in range(count):\n",
    "            node = q.popleft()\n",
    "            if node.left != None:\n",
    "                q.append(node.left)\n",
    "            if node.right != None:\n",
    "                q.append(node.right)\n",
    "        res = max(res, count)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c8a0c14",
   "metadata": {},
   "source": [
    "## Convert Tree to Doubly Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "f37fd023",
   "metadata": {},
   "outputs": [],
   "source": [
    "prev = None\n",
    "def convert(root):\n",
    "    if root is None:\n",
    "        return root\n",
    "    head = convert(root.left)\n",
    "    global prev\n",
    "    if prev is None:\n",
    "        head = root\n",
    "    else:\n",
    "        root.left = prev\n",
    "        prev.right = root\n",
    "    prev = root\n",
    "    convert(root.right)\n",
    "    return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "d284d725",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x26ce72212a0>"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "convert(root2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44434a25",
   "metadata": {},
   "source": [
    "## Construct Tree From Inorder and preorder\n",
    "\n",
    "Use inorder for left and right nodes and preorder for root node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "4eac0c6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# naive approach time complexity is O(N^2)\n",
    "def buildTree(pre_order, in_order, in_start_indx, in_end_indx):\n",
    "    if in_start_indx > in_end_indx:\n",
    "        return None\n",
    "    global pre_ind\n",
    "    root = Node(pre_order[pre_ind])\n",
    "    pre_ind += 1\n",
    "    \n",
    "    if (in_start_indx == in_end_indx):\n",
    "        return root\n",
    "    \n",
    "    for node in range(in_start_indx, in_end_indx + 1):\n",
    "        if in_order[node] == root.key:\n",
    "            break\n",
    "    # call for left and right nodes\n",
    "    root.left = buildTree(pre_order, in_order, in_start_indx, node - 1)\n",
    "    root.right = buildTree(pre_order, in_order, node + 1, in_end_indx)\n",
    "    \n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "8eb109fa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x26ce725c2b0>"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pre_ind = 0\n",
    "buildTree([20,10,40,30,50], [10,20,30,40,50], 0, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "7115c228",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Efficient Solution Using Dictionary / Mapping Function \n",
    "# the Time Complexity is O(N)\n",
    "mp = {}\n",
    "in_order = [10,20,30,40,50]\n",
    "pre_order = [20,10,40,30,50]\n",
    "# it make Map function which stores inorder value as a key and there index as the value\n",
    "def buildMap(in_order, mp):\n",
    "    for i in range(len(in_order)):\n",
    "        mp[in_order[i]] = i\n",
    "        \n",
    "buildMap(in_order, mp)\n",
    "# the main function which builds the tree \n",
    "# now the node calculation can be look in O(1) time which reduces our Time Complexity\n",
    "def buildTree(pre_order, in_order, in_start_idx, in_end_idx, mp):\n",
    "    if in_start_idx > in_end_idx:\n",
    "        return None\n",
    "    global pre_ind\n",
    "    root = Node(pre_order[pre_ind])\n",
    "    pre_ind += 1\n",
    "    \n",
    "    if (in_start_idx == in_end_idx):\n",
    "        return root\n",
    "    node = mp[root.key]\n",
    "    # call left and right\n",
    "    root.left = buildTree(pre_order, in_order, in_start_idx, node - 1, mp)\n",
    "    root.right = buildTree(pre_order, in_order, node + 1, in_end_idx, mp)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "c8a36293",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x26ce5cc8a00>"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pre_ind = 0\n",
    "buildTree(pre_order, in_order, 0 , len(in_order) - 1, mp)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9595a5a0",
   "metadata": {},
   "source": [
    "## Tree Traversal in Spiral Form\n",
    "\n",
    "\n",
    "    Input:                20\n",
    "                        /     \\\n",
    "                      8         22\n",
    "                   /      \\         \\\n",
    "                 5         3        25\n",
    "                       /    \\      \n",
    "                     10       14\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "d834eff3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def printSpiral(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    q = deque()\n",
    "    q.append(root)\n",
    "    alter = False\n",
    "    s = []\n",
    "    while q:\n",
    "        count = len(q)\n",
    "        for _ in range(count):\n",
    "            node = q.popleft()\n",
    "            if alter:\n",
    "                s.append(node.key)\n",
    "            else:\n",
    "                print(node.key, end=\" \")\n",
    "            if node.left != None:\n",
    "                q.append(node.left)\n",
    "            if node.right != None:\n",
    "                q.append(node.right)\n",
    "        # pop the elements from stack\n",
    "        if alter:\n",
    "            while s:\n",
    "                print(s.pop(), end= \" \")\n",
    "        alter = not alter\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "542d66d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "root2 = Node(20)\n",
    "root2.left = Node(8)\n",
    "root2.right = Node(22)\n",
    "root2.left.left = Node(5)\n",
    "root2.left.right = Node(3)\n",
    "root2.right.right = Node(25)\n",
    "root2.left.right.left = Node(10)\n",
    "root2.left.right.right = Node(14)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "da101c29",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20 22 8 5 3 25 14 10 "
     ]
    }
   ],
   "source": [
    "printSpiral(root2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fad5b219",
   "metadata": {},
   "source": [
    "### Improved one\n",
    "When i take out node from s1 and then we have to append into s2 in proper i.e left and right\n",
    "\n",
    "\n",
    "But when we take out node from s2 and then we have to append into s1 in reverse order i.e right and left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "81cdca2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def printSpiral2(root):\n",
    "    if root is None:\n",
    "        return root\n",
    "    s1 = []\n",
    "    s2 = []\n",
    "    s1.append(root)\n",
    "    while len(s1) != 0  or len(s2) != 0:\n",
    "        if len(s1) != 0:\n",
    "            for _ in range(len(s1)):\n",
    "                node = s1.pop()\n",
    "                print(node.key, end = \" \")\n",
    "                if node.left != None:\n",
    "                    s2.append(node.left)\n",
    "                if node.right != None:\n",
    "                    s2.append(node.right)\n",
    "        if len(s2) != 0:\n",
    "            for _ in range(len(s2)):\n",
    "                node = s2.pop()\n",
    "                print(node.key, end=\" \")\n",
    "                if node.right != None:\n",
    "                    s1.append(node.right)\n",
    "                if node.left != None:\n",
    "                    s1.append(node.left)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "282b1a3c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20 22 8 5 3 25 14 10 "
     ]
    }
   ],
   "source": [
    "printSpiral2(root2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a732076a",
   "metadata": {},
   "source": [
    "### It prints a level as a seperate array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "88f70bff",
   "metadata": {},
   "outputs": [],
   "source": [
    "def printSpiral3(root):\n",
    "    if root is None:\n",
    "        return root\n",
    "    s1 = []\n",
    "    s2 = []\n",
    "    row_ans = []\n",
    "    res = []\n",
    "    s1.append(root)\n",
    "    while len(s1) != 0  or len(s2) != 0:\n",
    "        if len(s1) != 0:\n",
    "            for _ in range(len(s1)):\n",
    "                node = s1.pop()\n",
    "                row_ans.append(node.key)\n",
    "                if node.left != None:\n",
    "                    s2.append(node.left)\n",
    "                if node.right != None:\n",
    "                    s2.append(node.right)\n",
    "        res.append(row_ans)\n",
    "        row_ans = []\n",
    "        if len(s2) != 0:\n",
    "            for _ in range(len(s2)):\n",
    "                node = s2.pop()\n",
    "                row_ans.append(node.key)\n",
    "                if node.right != None:\n",
    "                    s1.append(node.right)\n",
    "                if node.left != None:\n",
    "                    s1.append(node.left)\n",
    "        res.append(row_ans)\n",
    "        row_ans = []\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a872db3e",
   "metadata": {},
   "source": [
    "## Diameter of a Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "595507eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TC : O(N^2)\n",
    "def diameterTree(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    d1 = 1 + height(root.left) + height(root.right)\n",
    "    d2 = diameterTree(root.left) # returns the diameter of entire left subtree\n",
    "    d3 = diameterTree(root.right)\n",
    "    return max(d1,d2,d3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "c8a31884",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diameterTree(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "aa1ffa41",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Efficient Solution\n",
    "res = float(\"-inf\")\n",
    "def diameterTree2(root, res):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    lh = diameterTree2(root.left, res)\n",
    "    rh = diameterTree2(root.right, res)\n",
    "    res = max(res, 1 + rh + lh)\n",
    "    return 1 + max(lh, rh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "684b906d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diameterTree2(root2, res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f61f557",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Lowest Common Ancestor (LCA) of Binary Tree\n",
    "\n",
    "There are possible ways like there contains 2 values `a` and `b`\n",
    "1. if either `curr` == a or `curr` == b\n",
    "2. if a is present in left subtree and b is present in right subtree, then we return the `curr`\n",
    "3. both a & b in same subtree then return the highest\n",
    "4. Either a is not present in left subtree nor b is present return `null`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "f00e2f49",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Naive Solution as it takes 2 traversals to get the value of path\n",
    "def findPath(root, path, number):\n",
    "    if root is None:\n",
    "        return False\n",
    "    path.append(root.key)\n",
    "    if root.key == number:\n",
    "        return True\n",
    "    if (root.left != None and findPath(root.left, path, number) or \\\n",
    "       root.right != None and findPath(root.right, path, number)):\n",
    "        return True\n",
    "    path.pop()\n",
    "    return False\n",
    "\n",
    "\n",
    "def findLCA1(root, n1, n2):\n",
    "    p1 = []\n",
    "    p2 = []\n",
    "    if not findPath(root, p1, n1) or not findPath(root, p2, n2):\n",
    "        return None\n",
    "    i = 0\n",
    "    while i < len(p1) and i < len(p2):\n",
    "        if p1[i] != p2[i]:\n",
    "            break\n",
    "        i += 1\n",
    "    return p1[i-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "687c400c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findLCA1(root2,10,14)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "d9948886",
   "metadata": {},
   "outputs": [],
   "source": [
    "# The Efficient Solution as it takes only one traversal\n",
    "def LCA2(root, n1, n2):\n",
    "    if root is None:\n",
    "        return None\n",
    "    if root.key == n1 or root.key == n2: # if the data is same as n1 or n2 it returns the node itself \n",
    "        return root\n",
    "    lca1 = LCA2(root.left, n1, n2) # calls for left node\n",
    "    lca2 = LCA2(root.right, n1, n2) # calls for right node\n",
    "    if lca1 and lca2: # if both contains the value that means both node has same root\n",
    "                      # i.e left subtree has one n1 and right has one n2\n",
    "        return root # so it returns the parent to the root call\n",
    "    return lca1 if lca1 else lca2 # it checks if the lca1 contains a number if not returns the lca2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "b454ef1c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x26ce725c9d0>"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LCA2(root2,3,14)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02842b3e-aeb5-487f-bb07-fb4d384614dc",
   "metadata": {},
   "source": [
    "## Lowest Common Ancestor Of Deepest Leafes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "0134fb83-307b-4bdf-afd3-027f7052bea5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def LCADeepestLeaf(root):\n",
    "    def height(root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return 1 + max(height(root.left), height(root.right))\n",
    "    def dfs(root):\n",
    "        if root is None:\n",
    "            return None\n",
    "        left, right = height(root.left) , height(root.right)\n",
    "        if left == right:\n",
    "            return root\n",
    "        if left > right:\n",
    "            return dfs(root.left)\n",
    "        if left < right:\n",
    "            return dfs(root.right)\n",
    "    return dfs(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e32f1907",
   "metadata": {},
   "source": [
    "## Count Nodes in Complete Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "61dea3f2",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.left.left = Node(40)\n",
    "root.left.right = Node(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "bd191e14",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Naive Solution\n",
    "def countNodes(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    return 1 + countNodes(root.left) + countNodes(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "322731ee",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countNodes(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "1d2c1160",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Efficient Solution\n",
    "# We just go throeugh the left and right nodes and calulate if both are equal then \n",
    "# the tree is perfect binary tree\n",
    "# TC O(logn * logn)\n",
    "def countNodes2(root):\n",
    "    lh, rh = 0,0\n",
    "    curr = root\n",
    "    while curr:\n",
    "        lh += 1\n",
    "        curr = curr.left # for left\n",
    "    curr = root # reset the curr value as it is only used to increment lh counter\n",
    "    while curr:\n",
    "        rh += 1\n",
    "        curr = curr.right # for right\n",
    "    if lh == rh:\n",
    "        return (1 << lh) - 1 # it is basically 2 ** lh which results the same number 🤔 don't know why :(\n",
    "    return 1 + countNodes2(root.left) + countNodes(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "4187a8b5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countNodes2(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d4a5974",
   "metadata": {},
   "source": [
    "## Serialize and Desrialize\n",
    "\n",
    "* Serialize: Convert the root/tree to array such that we can convert back again into the Tree\n",
    "\n",
    "\n",
    "* DeSerialize: By using the array we convert into original tree\n",
    "\n",
    "<img src= \"https://media.geeksforgeeks.org/wp-content/uploads/serializationFile-1.jpg\"/>\n",
    "\n",
    "\n",
    "\n",
    "    Input:                20\n",
    "                        /     \\\n",
    "                      8         22\n",
    "                   /      \\         \\\n",
    "                 5         3        25\n",
    "                       /    \\      \n",
    "                     10       14\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "46b8d6f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def serialize(root, arr):\n",
    "    if root is None:\n",
    "        arr.append(-1)\n",
    "        return\n",
    "    arr.append(root.key)\n",
    "    serialize(root.left, arr)\n",
    "    serialize(root.right, arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "b8e9c444",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[20, 8, 5, -1, -1, 3, 10, -1, -1, 14, -1, -1, 22, -1, 25, -1, -1]\n"
     ]
    }
   ],
   "source": [
    "arr = []\n",
    "serialize(root2, arr)\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "cdc3eb47",
   "metadata": {},
   "outputs": [],
   "source": [
    "def deserialize(arr, index):\n",
    "    if index == len(arr):\n",
    "        return None\n",
    "    val = arr[index]\n",
    "    index += 1\n",
    "    if val == -1:\n",
    "        return None\n",
    "    root = Node(val)\n",
    "    root.left = deserialize(arr, index)\n",
    "    root.right = deserialize(arr, index)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "a47b4ffb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x26ce7253bb0>"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deserialize(arr, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8879ef96",
   "metadata": {},
   "source": [
    "## Iterative Inorder Traversal\n",
    "\n",
    "\n",
    "\n",
    "    Input:                20\n",
    "                        /     \\\n",
    "                      8         22\n",
    "                   /      \\         \\\n",
    "                 5         3        25\n",
    "                       /    \\      \n",
    "                     10       14\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "d9a98c09",
   "metadata": {},
   "outputs": [],
   "source": [
    "def iterativeInorder(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    st = []\n",
    "    curr = root\n",
    "    # append the left node in stack\n",
    "    while curr is not None:\n",
    "        st.append(curr)\n",
    "        curr = curr.left\n",
    "    while len(st) > 0:\n",
    "        curr = st.pop()\n",
    "        print(curr.key)\n",
    "        curr = curr.right\n",
    "        while curr is not None:\n",
    "            st.append(curr)\n",
    "            curr = curr.left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "0e5929f2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "8\n",
      "10\n",
      "3\n",
      "14\n",
      "20\n",
      "22\n",
      "25\n"
     ]
    }
   ],
   "source": [
    "iterativeInorder(root2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9083fb3",
   "metadata": {},
   "source": [
    "## Iterative PreOrder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "c967e451",
   "metadata": {},
   "outputs": [],
   "source": [
    "def iterativePreorder(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    st = [root]\n",
    "    while len(st) > 0:\n",
    "        curr = st.pop()\n",
    "        print(curr.key)\n",
    "        if curr.right is not None:\n",
    "            st.append(curr.right)\n",
    "        if curr.left is not None:\n",
    "            st.append(curr.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "33a3f1fb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "8\n",
      "5\n",
      "3\n",
      "10\n",
      "14\n",
      "22\n",
      "25\n"
     ]
    }
   ],
   "source": [
    "iterativePreorder(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "82a9dbfc",
   "metadata": {},
   "outputs": [],
   "source": [
    "def iterativePreorder_Efficient(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    st = []\n",
    "    curr = root\n",
    "    while st or curr != None:\n",
    "        while curr != None:\n",
    "            print(curr.key, end=\" \")\n",
    "            if curr.right != None:\n",
    "                st.append(curr.right)\n",
    "            curr = curr.left\n",
    "        if st:\n",
    "            curr = st.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "8505ebf2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20 8 5 3 10 14 22 25 "
     ]
    }
   ],
   "source": [
    "iterativePreorder_Efficient(root2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "742f86c6",
   "metadata": {},
   "source": [
    "## Left View of Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "id": "9963d432",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "#Function to return a list containing elements of left view of the binary tree.\n",
    "def LeftViewTraversal(root, res, level):\n",
    "    if root is None:\n",
    "        return res\n",
    "    if len(res) == level:\n",
    "        res.append(root.data)\n",
    "    LeftViewTraversal(root.left, res, level + 1)\n",
    "    LeftViewTraversal(root.right, res, level + 1)\n",
    "    \n",
    "def LeftView(root):\n",
    "    res = []\n",
    "    if root is None:\n",
    "        return res\n",
    "    LeftViewTraversal(root, res, 0)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5131b5d",
   "metadata": {},
   "source": [
    "## Left View Traversal using HashMap\n",
    "\n",
    "* Just same as the Level Order Traversal we use `hashing` as we only print the value which is stored on first we doesn't update the hash value in Left View"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "004818e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def leftViewHash(root):\n",
    "    level = 0\n",
    "    mp = {}\n",
    "    LeftViewUtil(root, mp, level)\n",
    "    for i in mp.values():\n",
    "        print(i)\n",
    "def LeftViewUtil(root, mp, level):\n",
    "    if root is None:\n",
    "        return\n",
    "    if mp.get(level) == None:\n",
    "        mp[level] = root.key\n",
    "    LeftViewUtil(root.left, mp, level + 1)\n",
    "    LeftViewUtil(root.right, mp, level + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "467ed2c3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "20\n",
      "40\n"
     ]
    }
   ],
   "source": [
    "leftViewHash(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf9e2267",
   "metadata": {},
   "source": [
    "## Right View By using HashMap\n",
    "\n",
    "\n",
    "* Just same as the Level Order Traversal we use `hashing` as we only print the value which is stored on first we update the hash value in Right View"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "2baac184",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rightBViewHash(root):\n",
    "    level = 0\n",
    "    mp = {}\n",
    "    rightViewHashUtil(root, mp, level)\n",
    "    for i in mp.values():\n",
    "        print(i)\n",
    "def rightViewHashUtil(root, mp, level):\n",
    "    if root is None:\n",
    "        return\n",
    "    if mp.get(level) == None:\n",
    "        mp[level] = root.key\n",
    "    else:\n",
    "        mp[level] = root.key\n",
    "    rightViewHashUtil(root.left, mp, level + 1)\n",
    "    rightViewHashUtil(root.right, mp, level + 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "2757d5df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "30\n",
      "50\n"
     ]
    }
   ],
   "source": [
    "rightBViewHash(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77d78c1d",
   "metadata": {},
   "source": [
    "## Vertical Width of a Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "4cea8b9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from collections import deque\n",
    "\n",
    "#Function to find the vertical width of a Binary Tree.\n",
    "def verticalWidth(root):\n",
    "    # code here\n",
    "    if root is None:\n",
    "        return 0\n",
    "    mp = {}# to store the mapped values\n",
    "    q = deque()\n",
    "    q1 = deque()\n",
    "    q.append(root)\n",
    "    q1.append(0)\n",
    "    while q:\n",
    "        curr = q.popleft()\n",
    "        hd = q1.popleft()\n",
    "        \n",
    "        if mp.get(hd) is None:\n",
    "            mp[hd] = []\n",
    "        mp[hd].append(curr.data)\n",
    "        if curr.left != None:\n",
    "            q.append(curr.left)\n",
    "            q1.append(hd - 1) # when we go left we reduce by 1\n",
    "        if curr.right != None:\n",
    "            q.append(curr.right)\n",
    "            q1.append(hd + 1) # when we go right we increase by 1\n",
    "    return len(mp.keys())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "ec1174b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "mp = {0: [3, 15], -1: [9], 1: [20], 2: [7]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "a51e6a94",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "eebe01dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted_mp = [-1,0,1,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "54e7d57a",
   "metadata": {},
   "outputs": [],
   "source": [
    "temp = []\n",
    "ans = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "fb741973",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3]\n",
      "[3, 15]\n",
      "[9]\n",
      "[20]\n",
      "[7]\n"
     ]
    }
   ],
   "source": [
    "for i in mp.keys():\n",
    "    for j in range(len(sorted(mp[i]))):\n",
    "#         print(mp[i])\n",
    "        temp.append(mp[i][j])\n",
    "        print(temp)\n",
    "    ans.append(temp)\n",
    "    temp = []\n",
    "#     return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c695ddb",
   "metadata": {},
   "source": [
    "## Create Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "f4dcf519",
   "metadata": {},
   "outputs": [],
   "source": [
    "def createTree():\n",
    "#     print(, flush=True)\n",
    "    data = int(input(\"Enter Data\"))\n",
    "    if data == -1:\n",
    "        return None\n",
    "    node = Node(data)\n",
    "    print(f\"Enter left of {data}\")\n",
    "    node.left = createTree()\n",
    "    print(f\"Enter right of {data}\")\n",
    "    node.right = createTree()\n",
    "    return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "de822da4",
   "metadata": {},
   "outputs": [],
   "source": [
    "root = Node(5)\n",
    "root.left = Node(10)\n",
    "root.right = Node(20)\n",
    "root.left.left = Node(30)\n",
    "root.left.right = Node(40)\n",
    "root.right.left = Node(80)\n",
    "root.right.right = Node(60)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a3da11c",
   "metadata": {},
   "source": [
    "## Print Value in Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "4544a237",
   "metadata": {},
   "outputs": [],
   "source": [
    "def printVal(root):\n",
    "    if root == None:\n",
    "        return None\n",
    "    printVal(root.left)\n",
    "    print(root.key)\n",
    "    printVal(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "706efa1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# printVal(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0070cf9f",
   "metadata": {},
   "source": [
    "## Level Order Traversal Seperate LIne"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "772badc6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def level_order_Traversal_line(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    q = deque()\n",
    "    q.append(root)\n",
    "    while q:\n",
    "        count = len(q)\n",
    "        for _ in range(count):\n",
    "            node = q.popleft()\n",
    "            print(node.key,end=\" \")\n",
    "            if node.left != None:\n",
    "                q.append(node.left)\n",
    "            if node.right != None:\n",
    "                q.append(node.right)\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "ef44f2e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 \n",
      "10 20 \n",
      "30 40 80 60 \n"
     ]
    }
   ],
   "source": [
    "level_order_Traversal_line(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8131e095-931a-4811-ba67-060ba3bb8efb",
   "metadata": {},
   "source": [
    "## Flatten Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "4802383e-cd59-46a3-9725-c6a4af5c87ed",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "root = Node(10)\n",
    "root.left = Node(20)\n",
    "root.right = Node(30)\n",
    "root.left.left = Node(40)\n",
    "root.left.right = Node(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "17163498-2c29-43d3-bddc-ebb13a18f695",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def flattenBinaryTree(root):\n",
    "    \"\"\"\n",
    "    Don't return anything modify inplace\n",
    "    \"\"\"\n",
    "    def dfs(root):\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        leftTail = dfs(root.left)\n",
    "        rightTail = dfs(root.right)\n",
    "        \n",
    "        if root.left:\n",
    "            leftTail.right = root.right\n",
    "            # this is the main part where matter occurs\n",
    "            root.right = root.left\n",
    "            root.left = None\n",
    "            # if rightTail is None and left Tail is None thenit will return root\n",
    "            # if rightTail is notNull then it directly return without comparing others\n",
    "        last = rightTail or leftTail or root\n",
    "        return last\n",
    "    dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "af3ee07b-736d-450c-add5-912d4338eb99",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "flattenBinaryTree(root)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f096c9c6-dcb5-4338-b37a-53db32509c00",
   "metadata": {},
   "source": [
    "## Burn a Binary Tree <img src=\"https://em-content.zobj.net/source/animated-noto-color-emoji/356/fire_1f525.gif\" width=30 height=20/> (Doubt 🀄)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "2e04e401-2eae-45bd-b363-6b3a05fe7ae0",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def burnBinaryTree(root, leaf, dist):\n",
    "    global res\n",
    "    if root is None:\n",
    "        return 0\n",
    "    if root.key == leaf:\n",
    "        dist[0] = 1\n",
    "        return 1\n",
    "    ld , rd= [-1],[-1]\n",
    "    lh = burnBinaryTree(root.left, leaf, ld)\n",
    "    rh = burnBinaryTree(root.right, leaf, rd)\n",
    "    if ld[0] != -1:\n",
    "        dist[0] = ld[0] + 1\n",
    "        res = max(res, dist[0] + rh)\n",
    "    if rd[0] != -1:\n",
    "        dist[0] = rd[0] + 1\n",
    "        res = max(res, dist[0] + lh)\n",
    "    return max(lh, rh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "9949173a-441e-4e63-b4a3-7563a59e60ba",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist = [-1]\n",
    "res = -1\n",
    "burnBinaryTree(root, 30, dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "107dcfed-b039-47d3-bb58-604328407563",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# root = createTree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "038836f7-13d2-4d60-9483-137e0363ce47",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Node at 0x26ce7253700>"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "30162db0-3e6f-40ad-91ce-e8b0be727cac",
   "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.10.10"
  },
  "toc-autonumbering": false,
  "toc-showcode": false,
  "toc-showmarkdowntxt": false,
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}