1448. Count Good Nodes in Binary 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.

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:

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

2. 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:

1def goodNodes(self, root: TreeNode) -> int:
2    def dfs(root: TreeNode, mx: int):
3        # rest of the dfs implementation
4
5    ans = 0
6    dfs(root, -1000000)  # Start the DFS with the root node and a min initial value
7    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.

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:

1       3
2      / \
3     1   4
4    /   / \
5   3   1   5

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.

1. We start the DFS with the root node (value 3) and the minimum initial value as mx = -1000000.

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

3. Recursively call DFS on the left child (value 1) with mx = 3 (the value of the root node, since it was larger).

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

5. Recursively call DFS on the left child's left child (value 3) with mx = 3.

6. This left child's left child's value (3) is equal to mx, so it's a "good" node. Increment ans to 2.

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

8. The right child's value (4) is greater than mx, so it's "good". Increment ans to 3 and update mx to 4.

9. Recursively call DFS on the right child's left child (value 1) with mx = 4.

10. The right child's left child's value (1) is not greater than mx = 4. We do not increment ans.

11. Recursively call DFS on the right child's right child (value 5) with mx = 4.

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

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.