:orphan:

Diameter of Binary Tree
=======================

.. highlight:: none

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

Given the ``root`` of a binary tree, return *the length of the*
**diameter** *of the tree*.

The **diameter** of a binary tree is the **length** of the longest path
between any two nodes in a tree. This path may or may not pass through
the ``root``.

The **length** of a path between two nodes is represented by the number
of edges between them.

**Example 1:**

|image1|

::

   Input: root = [1,2,3,4,5]
   Output: 3
   Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

**Example 2:**

::

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

**Constraints:**

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

.. |image1| image:: https://assets.leetcode.com/uploads/2021/03/06/diamtree.jpg

.. highlight:: python

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

Approaches
----------

.. tab-set::

    .. tab-item:: DFS

        **Code**

        .. literalinclude:: ../problems/easy/diameter-of-binary-tree/diameter_of_binary_tree__dfs.py
            :language: python
            :lines: 9-

        **Test**

        >>> from diameter_of_binary_tree__dfs import TreeNode, diameterOfBinaryTree
        >>> diameterOfBinaryTree(TreeNode.from_list([1, 2, 3, 4, 5]))
        3
        >>> diameterOfBinaryTree(TreeNode.from_list([1, 2]))
        1

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

        .. autofunction:: diameter_of_binary_tree__dfs.diameterOfBinaryTree