1448. Count Good Nodes in Binary Tree

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Description

The problem requires counting the "good" nodes in a binary tree. A "good" node is defined as a node where, along the path from the root of the tree to that node, there are no nodes with a value greater than the value of the node itself. To simplify, if you start at the root and walk towards the node, every ancestor's value you encounter must be less than or equal to the node's value for it to be considered good. We must traverse the tree and count how many such good nodes exist.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here’s a step-by-step overview:

Is it a graph?

Yes: A binary tree is a specific type of graph.

Is it a tree?

Yes: The problem explicitly mentions that we are dealing with a binary tree.

Based on the flowchart, using Depth-First Search (DFS) is appropriate once confirming that the structure is a tree. This makes sense for the problem, as it entails traversing the tree and checking a condition for each node.

Conclusion: The flowchart confirms that DFS is a suitable choice for traversing the binary tree to count good nodes, owing to the tree structure of the graph.

Intuition

The key to solving this problem is to maintain the max value encountered along the path from the root to the current node. We perform a depth-first search (DFS) traversal of the tree and carry the maximum value found so far to each node's children. At each node, we do two checks:

If the current node's value is greater than or equal to the max value we've seen so far on this path, it qualifies as a good node, and we increment our count of good nodes. We also update the max value to the current node's value, because it's now the highest value seen on the path for the subtree rooted at this node.
We continue to traverse the tree by going left and right, carrying forward this updated max value to be used for the node's children.

The code defines a recursive dfs function that takes the current node and the current max value as parameters. If the node is None, we've hit a leaf's child, and there's nothing more to do, so we return. If the node is good, we increment our global answer ans by 1 and update the max value if necessary. Then we call dfs on the left and right children, ensuring that we pass the potentially updated max value. The code starts with a max value initialized to a very small number to ensure that the root node is always considered good (since there's no value in the tree less than this initial value).

The global variable ans is used to retain the count of good nodes found during the DFS traversal. After the traversal is completed, ans will store the total number of good nodes, and it's returned by the goodNodes function as the final answer.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a Depth-First Search (DFS) algorithm to traverse the tree. DFS is a common tree traversal technique that explores as far as possible along each branch before backtracking. This allows the solution to keep track of the current path's maximum value and check for "good" nodes.

The given Python code defines a nested dfs function within the goodNodes method. The dfs function is responsible for traversing the tree. It is called recursively for the root node initially, with the lowest possible integer value mx set as the initial maximum value (-1000000) encountered along the path. This is to ensure that the root node is always considered as a “good” node, since its value will certainly be higher than this minimum value.

The data structure used here is the given binary tree structure with TreeNode objects. Each TreeNode object contains a value val, and two pointers, left and right, pointing to its child nodes.

Here's what happens in the recursive dfs function:

The function receives a TreeNode object and the current path's max value mx.
It first checks if the current node is None. If so, the recursion ends (base case).
If the current node is not None, it checks if the node's value is greater than or equal to mx. If it is, it increments the counter variable ans by 1 since this node is "good".
The maximum value mx may be updated to the current node's value if it is indeed higher.
The dfs function is then recursively called with the left child of the current node and the updated max value, followed by the recursive call with the right child and the updated max value.

This process continues recursively, visiting all the nodes in the tree, checking each node's value against the maximum value seen so far along that path, and updating the count of good nodes in the global ans variable. After the DFS is completed, ans will hold the count of all good nodes, which is then returned by the goodNodes method.

Here's an example of how the dfs function is defined within the goodNodes method, and how it gets called initially:

def goodNodes(self, root: TreeNode) -> int:
    def dfs(root: TreeNode, mx: int):
        # rest of the dfs implementation

    ans = 0
    dfs(root, -1000000)  # Start the DFS with the root node and a min initial value
    return ans

This DFS pattern, combined with the use of a recursive helper function and a global counter variable, encapsulates the desired logic in a clean and efficient manner to solve the task at hand.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's run through a small example using a binary tree to illustrate the solution approach outlined. Suppose we have the following binary tree:

We want to count the number of "good" nodes in this tree. A node is "good" if no value greater than that node's value is encountered from the root to that node itself.

We start the DFS with the root node (value 3) and the minimum initial value as mx = -1000000.
Since the root node's value (3) is greater than mx, we count it as a "good" node. The "good" nodes count ans is now 1.
Recursively call DFS on the left child (value 1) with mx = 3 (the value of the root node, since it was larger).
The left child's value (1) is not greater than the current mx = 3, so we do not increment ans. The "good" nodes count remains 1.
Recursively call DFS on the left child's left child (value 3) with mx = 3.
This left child's left child's value (3) is equal to mx, so it's a "good" node. Increment ans to 2.
Since the left child (value 1) has no right child, we backtrack and continue the DFS on the right child of the root (value 4) with mx = 3.
The right child's value (4) is greater than mx, so it's "good". Increment ans to 3 and update mx to 4.
Recursively call DFS on the right child's left child (value 1) with mx = 4.
The right child's left child's value (1) is not greater than mx = 4. We do not increment ans.
Recursively call DFS on the right child's right child (value 5) with mx = 4.
The right child's right child's value (5) is greater than mx, so it's "good". Increment ans to 4 and update mx to 5.

Now that the entire tree has been traversed, we can conclude that there are 4 "good" nodes in this tree.

Hence, the goodNodes method will return 4, which is the total count of good nodes for this example binary tree.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def goodNodes(self, root: TreeNode) -> int:
10        # Inner function to perform depth-first search (DFS) on the tree.
11        def dfs(node: TreeNode, max_val: int):
12            # Base case: if the current node is None, return from the function.
13            if node is None:
14                return
15          
16            # Using nonlocal keyword to modify the 'good_nodes_count'
17            # variable defined in the parent function's scope
18            nonlocal good_nodes_count
19          
20            # If the current node's value is greater than or equal
21            # to the max value encountered so far, it is a 'good' node.
22            if max_val <= node.val:
23                # Increment count of 'good' nodes.
24                good_nodes_count += 1
25                # Update max value to current node's value.
26                max_val = node.val
27          
28            # Recursively call dfs for the left child with updated max value.
29            dfs(node.left, max_val)
30            # Recursively call dfs for the right child with updated max value.
31            dfs(node.right, max_val)
32
33        # Initialize count of 'good' nodes to 0.
34        good_nodes_count = 0
35        # Invoke dfs with the root of the tree and a very small initial max value.
36        dfs(root, float('-inf'))
37        # Return final count of 'good' nodes.
38        return good_nodes_count
39

1// Definition for a binary tree node.
2class TreeNode {
3    int val;         // Value of the node
4    TreeNode left;   // Reference to the left child
5    TreeNode right;  // Reference to the right child
6  
7    // Constructor for a tree node with no children
8    TreeNode() {}
9
10    // Constructor for a tree node with a specific value
11    TreeNode(int value) { this.val = value; }
12
13    // Constructor for a tree node with a value and references to left and right children
14    TreeNode(int value, TreeNode leftChild, TreeNode rightChild) {
15        this.val = value;
16        this.left = leftChild;
17        this.right = rightChild;
18    }
19}
20
21public class Solution {
22    private int numGoodNodes = 0; // Variable to keep count of good nodes
23
24    // Public method that starts the depth-first search and returns the number of good nodes
25    public int goodNodes(TreeNode root) {
26        dfsHelper(root, Integer.MIN_VALUE);
27        return numGoodNodes;
28    }
29
30    // Helper method that performs a depth-first search on the tree
31    private void dfsHelper(TreeNode node, int maxSoFar) {
32        if (node == null) {
33            return; // Base case: if the node is null, return
34        }
35        if (maxSoFar <= node.val) {
36            // If the current value is greater than or equal to the maximum value so far,
37            // it is a good node, so increment the counter and update the maximum value
38            numGoodNodes++;
39            maxSoFar = node.val;
40        }
41        dfsHelper(node.left, maxSoFar); // Recursively call helper for left subtree
42        dfsHelper(node.right, maxSoFar); // Recursively call helper for right subtree
43    }
44}
45

1#include <algorithm> // For using max function
2#include <functional> // For std::function
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {} // default constructor
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // constructor with value
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} // constructor with value and left, right nodes
12};
13
14class Solution {
15public:
16    int goodNodes(TreeNode* root) {
17        int countOfGoodNodes = 0; // This will keep track of the number of good nodes
18
19        // Depth First Search function that traverses the tree.
20        // It maintains the maximum value seen so far on the path from the root to the current node.
21        std::function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int maxValueSoFar) {
22            if (!node) {
23                return; // Base case: if the node is null, return
24            }
25            // If the current node's value is greater than or equal to the max value seen so far,
26            // increment the count of good nodes and update the max value for the path.
27            if (maxValueSoFar <= node->val) {
28                ++countOfGoodNodes;
29                maxValueSoFar = node->val;
30            }
31            // Continue the DFS traversal on the left and right children of the current node.
32            dfs(node->left, maxValueSoFar);
33            dfs(node->right, maxValueSoFar);
34        };
35
36        // Start the DFS with the initial max value as the minimum possible integer value.
37        dfs(root, INT_MIN);
38
39        return countOfGoodNodes; // Return the final count of good nodes.
40    }
41};
42

1// Global variable to keep track of the number of good nodes
2let goodNodesCount: number = 0;
3
4/**
5 * Represents a node in a binary tree.
6 */
7class TreeNode {
8    val: number;
9    left: TreeNode | null;
10    right: TreeNode | null;
11
12    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
13        this.val = val;
14        this.left = left;
15        this.right = right;
16    }
17}
18
19/**
20 * Calculate the number of good nodes in a binary tree.
21 * A good node is a node that is the largest value from root to the node itself.
22 * 
23 * @param {TreeNode | null} node - The node to start the deep-first search from.
24 * @param {number} maxSoFar - The largest value encountered from the root to the current node.
25 */
26function traverseAndCountGoodNodes(node: TreeNode | null, maxSoFar: number): void {
27    if (!node) {
28        return;
29    }
30    if (maxSoFar <= node.val) {
31        goodNodesCount++;
32        maxSoFar = node.val; // Update maxSoFar if the current node has a higher value
33    }
34    // Traverse left and right subtrees
35    traverseAndCountGoodNodes(node.left, maxSoFar);
36    traverseAndCountGoodNodes(node.right, maxSoFar);
37}
38
39/**
40 * Entry function to count the number of good nodes in a binary tree starting from the root.
41 *
42 * @param {TreeNode | null} root - The root node of the binary tree.
43 * @returns {number} - The count of good nodes.
44 */
45function goodNodes(root: TreeNode | null): number {
46    goodNodesCount = 0; // Reset the global count for good nodes
47    traverseAndCountGoodNodes(root, -Infinity); // Start DFS with the lowest possible value
48    return goodNodesCount; // Return the count of good nodes
49}
50

Time and Space Complexity

The provided Python code defines a function goodNodes that counts the number of "good" nodes in a binary tree. A "good" node is defined as a node whose value is greater than or equal to all the values in the nodes that lead to it from the root. The function implements a depth-first search (DFS) to traverse the tree and count these nodes.

Time Complexity

The time complexity of the code is determined by how many nodes are visited during the DFS traversal. The function visits every node exactly once. Therefore, the time complexity is O(N), where N is the number of nodes in the tree.

Space Complexity

The space complexity is primarily determined by the call stack due to the recursive nature of the DFS. In the worst-case scenario (a skewed tree), the depth of the recursive call stack can become O(N) if the tree is a linear chain of N nodes. In the average case of a balanced tree, the height would be O(logN), resulting in O(logN) recursive calls at any given time. However, since we need to consider the worst case, the space complexity of the code is O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know