---
# System prepended metadata

title: 1448. Count Good Nodes in Binary Tree
tags: [Leetcode, BFS, DFS, Medium, Microsoft]

---

# 1448. Count Good Nodes in Binary Tree
###### tags: `Leetcode` `Microsoft` `Medium` `DFS` `BFS`
Link: https://leetcode.com/problems/count-good-nodes-in-binary-tree/
## Code
BFS O(N) O(N)
```java=
class Solution {
    class GoodNode{
        int maxVal;
        TreeNode node;
        public GoodNode(int maxVal, TreeNode node){
            this.maxVal = maxVal;
            this.node = node;
        }
    }
    public int goodNodes(TreeNode root) {
        int count = 0;
        Queue<GoodNode> q = new LinkedList<>();
        q.add(new GoodNode(Integer.MIN_VALUE,root));
        while(!q.isEmpty()){
            GoodNode gn = q.poll();
            if(gn.maxVal<=gn.node.val){
                count++;
            }
            if(gn.node.left!=null) q.add(new GoodNode(Math.max(gn.maxVal,gn.node.val), gn.node.left));
            if(gn.node.right!=null) q.add(new GoodNode(Math.max(gn.maxVal,gn.node.val), gn.node.right));
        }
        return count;
    }
}
```