{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

104. Maximum Depth level of Binary Tree

\n", "
\n", "\n", "\n", "

Given the root of a binary tree, return its maximum depth the level of the farthest leaf (i.e. the height +1 of the tree).

\n", "\n", "

A binary tree's maximum depth level is the number of nodes along the longest path from the root node down to the farthest leaf node (see here for a reminder on the difference between depth, level and height)

\n", "\n", "

 

\n", "

Example 1:

\n", "\"\"\n", "
Input: root = [3,9,20,null,null,15,7]\n",
    "Output: 3\n",
    "
\n", "\n", "

Example 2:

\n", "\n", "
Input: root = [1,null,2]\n",
    "Output: 2\n",
    "
\n", "\n", "

Example 3:

\n", "\n", "
Input: root = []\n",
    "Output: 0\n",
    "
\n", "\n", "

Example 4:

\n", "\n", "
Input: root = [0]\n",
    "Output: 1\n",
    "
\n", "\n", "

 

\n", "

Constraints:

\n", "\n", "\n", "\n", "\n", "

 

\n", "Source \n", "
" ] }, { "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": [ "

Code

" ] }, { "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": [ "
\n", "

Follow up:

\n", "

Solve it both recursively and iteratively.

\n", "\n", "

Code

" ] }, { "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 }