1448. Count Good Nodes in Binary Tree - Leetcode Solution

Leetcode Problem Link Code Solution Link:

💡 Step-by-Step Thought Process

Solution Explanation

The problem asks to count the number of "good" nodes in a binary tree, where a node is good if its value is greater than or equal to the maximum value on the path from the root to that node.

The solution uses an iterative depth-first search (DFS) with a stack to traverse the tree and track the maximum value along each path. Here’s how it works:

Initialization: We initialize a counter good_nodes to 0 and a stack with the root node and an initial maximum value of negative infinity (to ensure the root is always good).
Iterative Traversal: While the stack is not empty, pop a node and its associated maximum value (largest):
- If the node’s value is at least largest, increment good_nodes, as the node is good.
- Update largest to the maximum of the current largest and the node’s value, as this is the new maximum for the path to the node’s children.
- Push the right and left children (if they exist) onto the stack, along with the updated largest.
Result: Return good_nodes, the total count of good nodes.
Why This Works: The stack-based DFS ensures we visit each node exactly once, and by passing the maximum value seen along the path to each node, we can determine if the node is good by comparing its value to this maximum. The initial negative infinity ensures the root node is always counted, and updating the maximum at each step correctly tracks the path’s maximum for child nodes.
Time and Space Complexity: The solution visits each node once, so the time complexity is O(n), where n is the number of nodes. The stack stores at most O(h) nodes, where h is the tree’s height, which is O(n) in the worst case (e.g., a skewed tree), so the space complexity is O(n).

Code Solution

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        good_nodes = 0
        stk = [(root, float("-inf"))]

        while stk:
            node, largest = stk.pop()
            
            if largest <= node.val:
                good_nodes += 1

            largest = max(largest, node.val)
            if node.right: stk.append((node.right, largest))
            if node.left: stk.append((node.left, largest))

        return good_nodes

# Time Complexity: O(n)
# Space Complexity: O(n)

#include <stack>
#include <algorithm>
using namespace std;

class Solution {
public:
    int goodNodes(TreeNode* root) {
        if (!root) return 0;

        int goodNodes = 0;
        stack<pair<TreeNode*, int>> stk;
        stk.push({root, INT_MIN});

        while (!stk.empty()) {
            auto [node, largest] = stk.top();
            stk.pop();

            if (largest <= node->val) {
                goodNodes++;
            }

            largest = max(largest, node->val);
            if (node->right) stk.push({node->right, largest});
            if (node->left) stk.push({node->left, largest});
        }

        return goodNodes;
    }
};

import java.util.Stack;

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

        int goodNodes = 0;
        Stack<Pair<TreeNode, Integer>> stk = new Stack<>();
        stk.push(new Pair<>(root, Integer.MIN_VALUE));

        while (!stk.isEmpty()) {
            Pair<TreeNode, Integer> pair = stk.pop();
            TreeNode node = pair.getKey();
            int largest = pair.getValue();

            if (largest <= node.val) {
                goodNodes++;
            }

            largest = Math.max(largest, node.val);
            if (node.right != null) stk.push(new Pair<>(node.right, largest));
            if (node.left != null) stk.push(new Pair<>(node.left, largest));
        }

        return goodNodes;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var goodNodes = function(root) {
    if (!root) return 0;

    let goodNodes = 0;
    const stk = [[root, -Infinity]];

    while (stk.length > 0) {
        const [node, largest] = stk.pop();

        if (largest <= node.val) {
            goodNodes++;
        }

        const newLargest = Math.max(largest, node.val);
        if (node.right) stk.push([node.right, newLargest]);
        if (node.left) stk.push([node.left, newLargest]);
    }

    return goodNodes;
};

Detailed Explanation

Get Personalized Support at AlgoMap Bootcamp 💡