# 1448, Count Good Nodes in Binary Tree - BFS

Nice graph problem from leetcode biweekly contest. As majority of graph problems this one can be solved with Breadth First Search as well.

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.

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.

To solve this problem:

- Perform a simple BFS over all nodes traversing from root to the leaves
- Keep track of Maximum along the path
- While queue is not empty, read the node
- Compare its value against max along the path
- If more than equal increase total count
- Calculate and pass down new max value

```
class Solution {
public int goodNodes(TreeNode root) {
var queue = new LinkedList<Node>();
int count = 0;
queue.add(new Node(root, root.val));
while(!queue.isEmpty()) {
var cur = queue.removeFirst();
if(cur.node == null) {
continue;
}
if(cur.node.val >= cur.max) {
count++;
}
queue.add(new Node(cur.node.left, Math.max(cur.node.val, cur.max)));
queue.add(new Node(cur.node.right, Math.max(cur.node.val, cur.max)));
}
return count;
}
private class Node {
TreeNode node;
int max;
Node(TreeNode node, int max) {
this.node = node;
this.max = max;
}
}
}
```