:orphan:

Balanced Binary Tree
====================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/balanced-binary-tree/

Given a binary tree, determine if it is height-balanced.

**Example 1:**

|image1|

::

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

**Example 2:**

|image2|

::

   Input: root = [1,2,2,3,3,null,null,4,4]
   Output: false

**Example 3:**

::

   Input: root = []
   Output: true

**Constraints:**

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

.. |image1| image:: https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2020/10/06/balance_2.jpg

.. highlight:: python

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

Approaches
----------

.. tab-set::

    .. tab-item:: DFS

        **Code**

        .. literalinclude:: ../problems/easy/balanced-binary-tree/balanced_binary_tree__dfs.py
            :language: python
            :lines: 11-

        **Test**

        >>> from balanced_binary_tree__dfs import TreeNode, isBalanced
        >>> isBalanced(TreeNode.from_list([3, 9, 20, None, None, 15, 7]))
        True
        >>> isBalanced(TreeNode.from_list([1, 2, 2, 3, 3, None, None, 4, 4]))
        False
        >>> isBalanced(TreeNode.from_list([]))
        True

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

        .. autofunction:: balanced_binary_tree__dfs.isBalanced