Valizada's blog

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.

test_sample_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.

To solve this problem:

  1. Perform a simple BFS over all nodes traversing from root to the leaves
  2. Keep track of Maximum along the path
  3. While queue is not empty, read the node
  4. Compare its value against max along the path
  5. If more than equal increase total count
  6. 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;
        }
    }
}