:orphan:

Count Good Nodes in Binary Tree
===============================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/count-good-nodes-in-binary-tree/

Given a binary tree ``root``, a node *X* in the tree is named **good**
if in the path from root to *X* there are no nodes with a value *greater
than* X.

Return the number of **good** nodes in the binary tree.

 

**Example 1:**

::


   Input: root = [3,1,4,3,null,1,5]
   Output: 4
   Explanation: Nodes in blue are good.
   Root Node (3) is always a good node.
   Node 4 -> (3,4) is the maximum value in the path starting from the root.
   Node 5 -> (3,4,5) is the maximum value in the path
   Node 3 -> (3,1,3) is the maximum value in the path.

**Example 2:**

::


   Input: root = [3,3,null,4,2]
   Output: 3
   Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

**Example 3:**

::


   Input: root = [1]
   Output: 1
   Explanation: Root is considered as good.

 

**Constraints:**

- The number of nodes in the binary tree is in the range ``[1, 10^5]``.
- Each node's value is between ``[-10^4, 10^4]``.

.. highlight:: python

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

Approaches
----------

.. tab-set::

    .. tab-item:: DFS

        **Code**

        .. literalinclude:: ../problems/medium/count-good-nodes-in-binary-tree/count_good_nodes_in_binary_tree__dfs.py
            :language: python
            :lines: 9-

        **Test**

        >>> from count_good_nodes_in_binary_tree__dfs import goodNodes, TreeNode
        >>> goodNodes(TreeNode.from_list([3, 1, 4, 3, None, 1, 5]))
        4
        >>> goodNodes(TreeNode.from_list([3, 3, None, 4, 2]))
        3

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

        .. autofunction:: count_good_nodes_in_binary_tree__dfs.good_nodes

        .. autofunction:: count_good_nodes_in_binary_tree__dfs.goodNodes