# Count Good Nodes in Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-good-nodes-in-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/count-good-nodes-in-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
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:**

**![](https://assets.glich.co/dsa/count-good-nodes-in-binary-tree/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/count-good-nodes-in-binary-tree/image1.png)**

**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]`.

# Approaches
## Depth-First Search with Path Tracking (Suboptimal)
This approach uses a Depth-First Search (DFS) traversal. As we traverse down the tree, we maintain a list of the values of the nodes in the current path from the root. For each node, we check if it's 'good' by finding the maximum value in the path list and comparing it with the node's own value.
**Time:** O(N * H), where N is the number of nodes and H is the height of the tree. We visit each of the N nodes. At each node, we iterate through the current path to find the maximum value. The path length can be up to H. In the worst case of a skewed tree, H can be N, leading to O(N^2) complexity. · **Space:** O(H), where H is the height of the tree. This space is used for the recursion stack and to store the `pathList`. In the worst case of a skewed tree, this becomes O(N).
**Pros:** Conceptually simple as it directly models the problem of checking the full path for each node.
**Cons:** Highly inefficient due to redundant computations. The maximum value of the path is recalculated at every node.; Higher time complexity compared to the optimal solution.; Requires careful implementation of backtracking.
### Explanation
In this method, we employ a recursive helper function that takes the current node and a list representing the path from the root to the node's parent. 

When visiting a node, we first iterate through the entire path list to find the maximum value among its ancestors. If the current node's value is greater than or equal to this maximum, we count it as a good node. After the check, we add the current node's value to the path list and make recursive calls for its children. 

Crucially, after the recursive calls for the children return (i.e., after exploring the entire subtree), we must remove the current node's value from the path list. This backtracking step ensures that the path list is correct for sibling nodes and their subtrees.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.ArrayList;
import java.util.List;

class Solution {
    int goodNodesCount = 0;

    public int goodNodes(TreeNode root) {
        if (root == null) return 0;
        // For the root, the path is empty, so any value is good.
        dfs(root, new ArrayList<>());
        return goodNodesCount;
    }

    private void dfs(TreeNode node, List<Integer> path) {
        if (node == null) {
            return;
        }

        // Check if the current node is good
        int maxInPath = Integer.MIN_VALUE;
        for (int val : path) {
            if (val > maxInPath) {
                maxInPath = val;
            }
        }

        if (node.val >= maxInPath) {
            goodNodesCount++;
        }

        // Recurse for children
        path.add(node.val);
        dfs(node.left, path);
        dfs(node.right, path);

        // Backtrack: remove the current node from the path
        path.remove(path.size() - 1);
    }
}
```
### Algorithm
*   Initialize a global counter for good nodes to 0.
*   Create a recursive helper function, e.g., `dfs(node, pathList)`.
*   The initial call is `dfs(root, new ArrayList<>())`.
*   Inside the helper function, if the `node` is null, return.
*   Find the maximum value in the `pathList`. If the list is empty (for the root), the max can be considered `Integer.MIN_VALUE`.
*   If `node.val` is greater than or equal to this maximum, increment the global counter.
*   Add `node.val` to the `pathList` to extend the path for its children.
*   Make recursive calls: `dfs(node.left, pathList)` and `dfs(node.right, pathList)`.
*   After the recursive calls return, backtrack by removing the last element from `pathList`.

## Optimal Tree Traversal (DFS or BFS)
The most efficient solution involves a single traversal of the tree, either Depth-First (DFS) or Breadth-First (BFS). The key insight is that instead of keeping track of the entire path to a node, we only need to know the maximum value encountered so far on that path. This maximum value can be passed down during the traversal, making the check at each node an O(1) operation.
**Time:** O(N) for both DFS and BFS variants, where N is the number of nodes. Each node is processed exactly once. · **Space:** *   **DFS:** O(H), where H is the height of the tree, due to the recursion stack. This is O(log N) for a balanced tree and O(N) for a skewed tree.
*   **BFS:** O(W), where W is the maximum width of the tree. This can be up to O(N) for a complete tree.
**Pros:** Optimal O(N) time complexity.; Efficient in terms of computation as it avoids redundant work.; Both DFS and BFS are standard, well-understood traversal algorithms.; The recursive DFS implementation is particularly concise and elegant.
**Cons:** The recursive DFS approach could theoretically cause a stack overflow on extremely deep and unbalanced trees, though this is unlikely in most contest platforms. The iterative BFS version mitigates this risk.
### Explanation
This approach optimizes the traversal by eliminating the need to re-scan the path for each node. We only need one piece of information from the ancestors: the maximum value seen so far.

### Depth-First Search (DFS) Approach

We can define a recursive helper function, `dfs(node, maxSoFar)`, that traverses the tree. The `maxSoFar` parameter stores the maximum value found on the path from the root to the current `node`'s parent. The initial call is made with the root node and a very small value (e.g., `Integer.MIN_VALUE`) as the initial `maxSoFar`. Inside the function, if the current `node.val` is greater than or equal to `maxSoFar`, we've found a good node and increment our count. Then, we update the maximum for the subsequent path: `newMax = Math.max(maxSoFar, node.val)` and make recursive calls for the left and right children using this `newMax`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }

    private int dfs(TreeNode node, int maxSoFar) {
        if (node == null) {
            return 0;
        }

        int count = 0;
        if (node.val >= maxSoFar) {
            count = 1;
        }

        // Update the max for the path to children
        int newMax = Math.max(maxSoFar, node.val);

        // Add the good nodes from the subtrees
        count += dfs(node.left, newMax);
        count += dfs(node.right, newMax);

        return count;
    }
}
```

### Breadth-First Search (BFS) Approach

An iterative BFS approach can also be used to achieve the same optimal performance and avoid deep recursion stacks. We use a queue that stores pairs of `(TreeNode, max_value_on_path)`. We start by adding the root and its path's maximum to the queue. We then loop while the queue is not empty. In each iteration, we dequeue a pair, check if the node is good, and then enqueue its children with the updated maximum path value.

```java
import java.util.Queue;
import java.util.LinkedList;

// Helper class for BFS
class Pair {
    TreeNode node;
    int maxSoFar;
    Pair(TreeNode node, int maxSoFar) {
        this.node = node;
        this.maxSoFar = maxSoFar;
    }
}

class Solution {
    public int goodNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int goodNodesCount = 0;
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(root, Integer.MIN_VALUE));

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            TreeNode node = current.node;
            int maxSoFar = current.maxSoFar;

            if (node.val >= maxSoFar) {
                goodNodesCount++;
            }

            int newMax = Math.max(maxSoFar, node.val);

            if (node.left != null) {
                queue.offer(new Pair(node.left, newMax));
            }
            if (node.right != null) {
                queue.offer(new Pair(node.right, newMax));
            }
        }

        return goodNodesCount;
    }
}
```
### Algorithm
### DFS Algorithm
*   Define a recursive helper function, `dfs(node, maxSoFar)`, that returns the count of good nodes in the subtree rooted at `node`.
*   The `maxSoFar` parameter tracks the maximum value on the path from the root to `node`'s parent.
*   **Base Case:** If `node` is null, return 0.
*   **Check Node:** Initialize a local `count`. If `node.val >= maxSoFar`, set `count` to 1, otherwise 0.
*   **Update Max:** Calculate the new maximum for the path to the children: `newMax = Math.max(maxSoFar, node.val)`.
*   **Recurse:** Add the results from the recursive calls on the children to the local `count`: `count += dfs(node.left, newMax) + dfs(node.right, newMax)`.
*   **Return:** Return the total `count`.
*   The initial call is `dfs(root, Integer.MIN_VALUE)`.

### BFS Algorithm
*   If `root` is null, return 0.
*   Initialize `count = 0` and a queue for `Pair(TreeNode, maxSoFar)` objects.
*   Add the initial pair `(root, Integer.MIN_VALUE)` to the queue.
*   Loop while the queue is not empty:
    *   Dequeue a pair `(currentNode, maxSoFar)`.
    *   If `currentNode.val >= maxSoFar`, increment `count`.
    *   Calculate `newMax = Math.max(maxSoFar, currentNode.val)`.
    *   If children exist, enqueue them with `newMax`: `queue.offer(new Pair(child, newMax))`.
*   Return the final `count`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans = 0 ; public int goodNodes ( TreeNode root ) { dfs ( root , - 100000 ); return ans ; } private void dfs ( TreeNode root , int mx ) { if ( root == null ) { return ; } if ( mx <= root . val ) { ++ ans ; mx = root . val ; } dfs ( root . left , mx ); dfs ( root . right , mx ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int goodNodes ( TreeNode * root ) { int ans = 0 ; function < void ( TreeNode * , int ) > dfs = [ & ]( TreeNode * root , int mx ) { if ( ! root ) { return ; } if ( mx <= root -> val ) { ++ ans ; mx = root -> val ; } dfs ( root -> left , mx ); dfs ( root -> right , mx ); }; dfs ( root , - 1e6 ); return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def goodNodes ( self , root : TreeNode ) -> int : def dfs ( root : TreeNode , mx : int ): if root is None : return nonlocal ans if mx <= root . val : ans += 1 mx = root . val dfs ( root . left , mx ) dfs ( root . right , mx ) ans = 0 dfs ( root , - 1000000 ) return ans
```