Count Good Nodes in Binary Tree

Problem Statement

In a given binary tree, the task is to identify nodes which are considered "good". A "good" node is defined as one where no ancestor (or no node in the path from the root to the node itself) has a value greater than the node's value. Essentially, for a node to qualify as "good", during the traversal from the root to this node, this node should be the highest value encountered or should at least tie with the highest. The problem's goal is to count and return how many such "good" nodes exist in the binary tree.

Examples

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

Approach and Intuition

The basic approach to find the "good" nodes relies on traversal techniques (DFS or BFS) to explore each node and compare its maximum ancestors’ values along the path. Here is a systematic breakdown of how one can approach this:

1. Initiate a Depth First Search traversal from the root. While traversing:

   • Note the maximum value found along the path from the root to each node.
   • Compare the current node’s value to this maximum path value.

2. If the current node’s value is greater than or equal to the recorded maximum for that particular path, it is considered a "good" node.

   • Update the count for "good" nodes.
   • Update the path's maximum value if the current node's value is greater than the previously recorded maximum.

3. Continue to traverse all branches of the tree:

   • For each node, recursively apply the same logic to all children nodes (left and right).
   • Pass the current path maximum to each child to ensure the context of "good" persists.

4. Upon completing the traversal of all nodes, the count will reflect the total number of "good" nodes in the binary tree.

Example Walkthroughs:

• For the tree structure given in example 1, start from the root node (3). As there's no comparison needed for the root itself, it's immediately a "good" node. Moving to the right child (4), since it’s greater than 3, it gets counted as "good". The same logic applies as you walk from the root to other nodes like 5 and the second 3 in the left subtree.
• Example 2 helps illustrate the exclusion case where the node value 2 does not count as "good" because there are higher values (3 and 4) on the path before it.
• Example 3 is straightforward since it involves only the root node, which is always "good" by default.

This approach efficiently allows identification of "good" nodes and adheres to the constraints provided, handling varying sizes and node values of the binary tree efficiently.

Solutions

class NodePair {
    public TreeNode treeNode;
    public int currentMax;

    public NodePair(TreeNode treeNode, int currentMax) {
        this.treeNode = treeNode;
        this.currentMax = currentMax;
    }
}

class Solution {
    public int goodNodes(TreeNode root) {
        int countGoodNodes = 0;
        Queue<NodePair> nodeQueue = new LinkedList<>();
        nodeQueue.offer(new NodePair(root, Integer.MIN_VALUE));

        while (!nodeQueue.isEmpty()) {
            NodePair current = nodeQueue.poll();
            if (current.currentMax <= current.treeNode.val) {
                countGoodNodes++;
            }

            if (current.treeNode.right != null) {
                nodeQueue.offer(new NodePair(current.treeNode.right, Math.max(current.treeNode.val, current.currentMax)));
            }

            if (current.treeNode.left != null) {
                nodeQueue.offer(new NodePair(current.treeNode.left, Math.max(current.treeNode.val, current.currentMax)));
            }
        }

        return countGoodNodes;
    }
}

class Solution:
    def countGoodNodes(self, root: TreeNode) -> int:
        good_node_count = 0
        from collections import deque  # Efficient queue operations

        node_queue = deque([(root, float("-inf"))])
        while node_queue:
            current, highest_value = node_queue.popleft()
            if highest_value <= current.val:
                good_node_count += 1
            if current.right:
                node_queue.append((current.right, max(current.val, highest_value)))
            if current.left:
                node_queue.append((current.left, max(current.val, highest_value)))
        
        return good_node_count