1448. Count Good Nodes in Binary Tree

Description

Given a binary tree, a node is considered a "good" node if the value of the node is greater than or equal to the maximum value in the path from the root to that node. The task is to count the number of good nodes in the tree.

Intuition

The intuition behind solving this problem is to traverse the tree while keeping track of the maximum value encountered along the current path. A node is considered "good" if its value is greater than or equal to this maximum value. We need to traverse the entire tree and count how many such nodes exist.

Approach

1. Tree Traversal: Use Depth-First Search (DFS) or a stack-based iterative approach to traverse the tree.
2. Track Maximum Value: While traversing, keep track of the maximum value seen so far on the path from the root to the current node.
3. Check Good Nodes: For each node, compare its value with the maximum value encountered on its path. If the node's value is greater than or equal to this maximum, it is a "good" node.
4. Update Maximum Value: Update the maximum value when moving to child nodes.
5. Count Good Nodes: Increment the count of good nodes each time a node qualifies as good.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the tree. Each node is visited once.

Space Complexity:

O(H), where H is the height of the tree. This is the space required by the call stack or the stack used for iterative traversal.

Code

C++

/**
 * 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) {
        if (!root) return 0;

        int numGoodNodes = 0;
        stack> st;
        st.push({root, INT_MIN});
        
        while (!st.empty()) {
            auto [node, maxVal] = st.top();
            st.pop();
            
            if (node->val >= maxVal) {
                numGoodNodes += 1;
                maxVal = node->val;
            }

            if (node->right) st.push({node->right, maxVal});
            if (node->left) st.push({node->left, maxVal});
        }

        return numGoodNodes;
    }
};

Python

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        if not root:
            return 0

        num_good_nodes = 0
        stack = [(root, float('-inf'))]
        
        while stack:
            node, max_val = stack.pop()
            if node.val >= max_val:
                num_good_nodes += 1
                max_val = node.val

            if node.left:
                stack.append((node.left, max_val))
            if node.right:
                stack.append((node.right, max_val))

        return num_good_nodes

Java

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

        int numGoodNodes = 0;
        Deque> stack = new ArrayDeque<>();
        stack.push(new Pair<>(root, Integer.MIN_VALUE));

        while (!stack.isEmpty()) {
            Pair current = stack.pop();
            TreeNode node = current.getKey();
            int maxVal = current.getValue();

            if (node.val >= maxVal) {
                numGoodNodes += 1;
                maxVal = node.val;
            }

            if (node.right != null) stack.push(new Pair<>(node.right, maxVal));
            if (node.left != null) stack.push(new Pair<>(node.left, maxVal));
        }

        return numGoodNodes;
    }
}

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var goodNodes = function (root) {
    if (!root) return 0;

    let numGoodNodes = 0;
    const stack = [];
    stack.push([root, -Infinity]);
    while (stack.length) {
        let [node, max] = stack.pop();
        const { left, right, val } = node;
        if (max <= val) {
            numGoodNodes += 1;
            max = val;
        }

        if (left) stack.push([left, max]);
        if (right) stack.push([right, max]);
    }

    return numGoodNodes;
};