{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>104. Maximum <strike>Depth</strike> level of Binary Tree</h1>\n",
    "<hr>\n",
    "\n",
    "<!--Copy Paste Leetcode statement between-->\n",
    "<p>Given the <code>root</code> of a binary tree, return <em><strike>its maximum depth</strike> the level of the farthest leaf (i.e. the height +1 of the tree)</em>.</p>\n",
    "\n",
    "<p>A binary tree's <strong>maximum <strike>depth</strike> level</strong>&nbsp;is the number of nodes along the longest path from the root node down to the farthest leaf node (see <a href=\"https://nbviewer.jupyter.org/github/adrien-perelloyb/leetcode/blob/main/lessons/tree_traversals.ipynb\">here</a> for a reminder on the difference between depth, level and height)</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<p><strong>Example 1:</strong></p>\n",
    "<img alt=\"\" src=\"./img1.jpeg\" style=\"width: 400px; height: 277px;\">\n",
    "<pre><strong>Input:</strong> root = [3,9,20,null,null,15,7]\n",
    "<strong>Output:</strong> 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>Example 2:</strong></p>\n",
    "\n",
    "<pre><strong>Input:</strong> root = [1,null,2]\n",
    "<strong>Output:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>Example 3:</strong></p>\n",
    "\n",
    "<pre><strong>Input:</strong> root = []\n",
    "<strong>Output:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>Example 4:</strong></p>\n",
    "\n",
    "<pre><strong>Input:</strong> root = [0]\n",
    "<strong>Output:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<p><strong>Constraints:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>The number of nodes in the tree is in the range <code>[0, 10<sup>4</sup>]</code>.</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n",
    "<!--Copy Paste Leetcode statement between-->\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<a href=\"https://leetcode.com/problems/maximum-depth-of-binary-tree/\">Source</a> \n",
    "<hr>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4>Code</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_height(root):\n",
    "    \"\"\"DFS using bottom up recursion\n",
    "    we dig until we reach a leaf (height = 0) and we add +1 for\n",
    "    each node until back to the root.\n",
    "    We return max(height(root)) = height(tree)\n",
    "    Note: the question asks for 1+height\n",
    "    \"\"\"\n",
    "    if not root:\n",
    "        return -1  # proper use of height\n",
    "    \n",
    "    left = max_height(root.left)\n",
    "    right = max_height(root.right)\n",
    "    return 1 + max(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_depth(root):\n",
    "    \"\"\"Same as above. This is what is actually asked for in this question\n",
    "    Though strictly speaking depth = counting edges and not nodes\n",
    "    Note: this solution CAN NOT be applied as such for min depth (see leetcode 111).\"\"\"\n",
    "    if not root:\n",
    "        return 0   # strictly speaking height(leaf) = 0 ==> height(None) should be -1 (by convention)\n",
    "    left = max_depth(root.left)\n",
    "    right = max_depth(root.right)\n",
    "    return 1 + max(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_depth(root):\n",
    "    \"\"\"Same as above.\n",
    "    Note: this solution CAN be applied as such for min depth (see leetcode 111).\"\"\"\n",
    "    if not root:\n",
    "        return 0  # strictly speaking height(None) should be -1\n",
    "    if not root.left and not root.right:        # not strictly\n",
    "        return 1                                # needed (but speeds up)\n",
    "    if not root.left:                           # However\n",
    "        return 1 + max_depth(root.right)        # it would be needed\n",
    "    if not root.right:                          # if we were looking for\n",
    "        return 1 + max_depth(root.left)         # min height instead\n",
    "    return 1 + max(max_depth(root.left), max_depth(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_depth(root):\n",
    "    \"\"\"DFS using Top down recursion\n",
    "    we dig into the tree, adding +1 at each children\n",
    "    until we reach a leaf, where we return the depth we calculated so far\n",
    "    we keep track of the highest value we saw so far\n",
    "    \"\"\"\n",
    "    def dfs(node, depth):\n",
    "        nonlocal max_depth\n",
    "        # base case\n",
    "        if not node:\n",
    "            if depth > max_depth:\n",
    "                max_depth = depth\n",
    "            return\n",
    "        depth += 1\n",
    "        left = dfs(node.left, depth)\n",
    "        right = dfs(node.right, depth)\n",
    "        return\n",
    "\n",
    "    max_depth = 0\n",
    "    dfs(root, 0)\n",
    "    return max_depth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "<h4>Follow up:</h4>\n",
    "<p>Solve it both recursively and iteratively.</p>\n",
    "\n",
    "<h4>Code</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_depth(root):\n",
    "    \"\"\"BFS using a top down iterative approach with a list.\"\"\"\n",
    "    if not root:\n",
    "        return 0\n",
    "    queue = [(root, 1)]\n",
    "    depth = 0\n",
    "    for (node, level) in queue:\n",
    "        if node:\n",
    "            depth = level  # last level we see will be the depth\n",
    "            queue += (node.left, level+1), (node.right, level+1),\n",
    "    return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def max_depth(root):\n",
    "    \"\"\"BFS using a top down iterative approach with a queue.\"\"\"\n",
    "    if not root:\n",
    "        return 0\n",
    "    queue = deque()\n",
    "    queue.append((root, 1))\n",
    "    depth = 0\n",
    "    while queue:\n",
    "        node, level = queue.popleft()\n",
    "        if node:\n",
    "            depth = level  # last level we see will be the depth\n",
    "            queue += (node.left, level+1), (node.right, level+1),\n",
    "    return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_level(root):\n",
    "    \"\"\"BFS using a bottom up iterative approach with a list.\"\"\"\n",
    "    # Start with a level traversal (using a stack)\n",
    "    queue = [root]\n",
    "    for node in queue:  \n",
    "        if node:\n",
    "            queue += node.left, node.right  # last nodes --> full layer of \"None\"\n",
    "\n",
    "    # then, traverse nodes in reverse (i.e from bottom layer)and update their height\n",
    "    # by conv. height of bottom nodes = 0 (i.e last nodes being \"None\" have depth = -1)\n",
    "    height = {None: -1}\n",
    "    for node in reversed(queue):\n",
    "        if node:\n",
    "            height_left = height[node.left]\n",
    "            height_right = height[node.right]\n",
    "            height[node] = 1 + max(height_left, height_right)\n",
    "    return 1+height[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def max_level(root):\n",
    "    \"\"\"BFS using a bottom up iterative approach  with a deque\"\"\"\n",
    "    queue = deque()\n",
    "    queue.append(root)\n",
    "    traversal = deque()\n",
    "    while queue:\n",
    "        node = queue.popleft()\n",
    "        if node:\n",
    "            traversal.appendleft(node)\n",
    "            queue += node.left, node.right  # last nodes --> full layer of \"None\"\n",
    "\n",
    "    height = {None: -1}\n",
    "    while traversal:\n",
    "        node = traversal.popleft()\n",
    "        if node:\n",
    "            height_left = height[node.left]\n",
    "            height_right = height[node.right]\n",
    "            height[node] = 1 + max(height_left, height_right)\n",
    "    return 1+height[root]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_depth(root):\n",
    "    \"\"\"DFS using an iterative approach with a stack.\"\"\"\n",
    "    if not root:\n",
    "        return 0\n",
    "    stack = [(root, 1)]\n",
    "    depth = 0\n",
    "    while stack:\n",
    "        (node, level) = stack.pop()\n",
    "        if node:\n",
    "            depth = max(depth, level)  # keep track of max depth\n",
    "            stack += (node.left, level+1), (node.right, level+1),\n",
    "    return depth"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}