:orphan:

Maximum Depth of Binary Tree
============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/maximum-depth-of-binary-tree/

Given the ``root`` of a binary tree, return *its maximum depth*.

A binary tree's **maximum depth** is the number of nodes along the
longest path from the root node down to the farthest leaf node.

 

**Example 1:**

|image1|

::


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

**Example 2:**

::


   Input: root = [1,null,2]
   Output: 2

 

**Constraints:**

- The number of nodes in the tree is in the range
  ``[0, 10``\ :sup:```4```\ ``]``.
- ``-100 <= Node.val <= 100``

.. |image1| image:: https://assets.leetcode.com/uploads/2020/11/26/tmp-tree.jpg

.. highlight:: python

Pattern
-------
Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution
--------
If ``root`` is ``None``, the height of a tree is 0. Otherwise, the height of a
tree is the 1 plus the maximum of the heights of the left and right subtrees.

Code
----

.. literalinclude:: ../problems/easy/maximum-depth-of-binary-tree/maximum_depth_of_binary_tree__approach_1.py
    :language: python
    :lines: 12-

Test
----
>>> from maximum_depth_of_binary_tree__approach_1 import TreeNode, maxDepth
>>> root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
>>> maxDepth(root)
3
>>> root = TreeNode(1, None, TreeNode(2))
>>> maxDepth(root)
2

Complexity
----------
| :math:`d` is the maximum depth of the tree
| Time: :math:`O(d)` — visit every node along the longest path from the root to a leaf
| Auxiliary Space: :math:`O(1)`

.. autoclass:: maximum_depth_of_binary_tree__approach_1.TreeNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: maximum_depth_of_binary_tree__approach_1.maxDepth