1448. Count Good Nodes in Binary Tree
Tags: algorithms, leetcode, binarytree
Published: 2024-03-11 03:55:19

**PROBLEM:**  
Given a binary tree root, a node X in the tree is named "good" if, in the path from the root to X, there are no nodes with a value greater than X.  
Return the number of good nodes in the binary tree.

**REASONING:**  
Let's say we are given this tree: [3,2,4,6,null,1,5].  
The tree's shape would look like this:

![Binary Tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yg36to4l4h4ci2e3lnpl.png)

The orange nodes are good nodes because there are no nodes in the path coming from the root to their position that have values greater than them.
- The root node 3 is a good node because the path from the root to its position only contains one node (itself), so there are no nodes in the path that are greater than it.
- Node 2 is not a good node because the path from the root to its position contains two nodes: 3 and 2, and there is a node that is greater than it, which is 3.
- The node 6 at the bottom is a good node because the path from the root to its position contains three nodes: 3, 2, and 6, and it is the greatest one along the path.

You can start to see the pattern, right? You go from the root to the end of one branch, checking for each node along the way if there is any node greater than it on the path that you have already passed. If there is not, you mark it as a good node and continue your path. 

The graph below shows the route that you should go through:


![Binary Tree with path direction](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sojtoke1zpagipqawdir.png)
 
You start from the root node. You check the left path by going through arrow 1 to node 2, then through arrow 2 to node 6. Along this path, you keep track of the maximum value. If any node is greater than or equal to the maximum value, you count it as a good node and update the maximum value to the node's value. Now, you reach the end of the left path, and you need to go back. 

You go back through arrow 3 to node 2, then through arrow 4 back to the root.  
Now, it's time to check the right path. You go through arrow 5 to node 4, then through arrow 6 to node 1. Along this path, you keep track of the maximum value. If any node is greater than or equal to the maximum value, you count it as a good node and update the maximum value to the node's value. Now, you reach the end of the first right path, and you need to go back.

You go back through arrow 7 back to node 4.  
Now, it's time to check the second right path. You go through arrow 8 to node 5. Along this path, you keep track of the maximum value. If any node is greater than or equal to the maximum value, you count it as a good node and update the maximum value to the node's value. Now, you reach the end of the second right path, and you need to go back.

You go back through arrow 9 back to node 4, then through arrow 10 back to the root.  
This is a depth-first search problem!

My initial approach was to set `count` to `0` and `max` to `-Infinity`. Then, consider the root node. If it is `null`, return. Otherwise, check if `max` is less than `root.val`. If it is (of course, it is. Any value is greater than `-Infinity`), update `max` to `root.val` and increase `count`. Then, do the same thing with the left node and right node consecutively. 

The solution should look like this:
```typescript
function goodNodes(root: TreeNode | null): number {
    let count = 0;
    let max = -Infinity;

    dfs(root);

    return count;

    function dfs(node: TreeNode | null) {
        if (node === null) return;

        if (max <= node.val) {
            count++;
            max = node.val;
        }

        dfs(node.left);
        dfs(node.right);
    }
}
```

There are two values that my code keeps track of along the way: `count` and `max`. Let's use the graph to see how it updates those values. 

![Binary tree with path direction and values](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/392flhqqls1nf8kp0bnn.png)
 
- You check the root node. Its value is greater than `max`, so you increase `count` from 0 to 1 and update `max` to 3 (equal to the value of the root node).
- You check node 2. Its value is less than `max`. You keep `count` and `max` the same.
- You check node 6. Its value is greater than `max`, so you increase `count` from 1 to 2 and update `max` to 6.
- You go back to node 2, then to node 3.

Now, you check node 4.  
Wait, there is something wrong here. Right before you check node 4 (at arrow 5), `max` should reflect the current maximum value of the current path, which is 3, not 6. Why is it still 6?

It turns out that when you go back one level, you need to update the `max` accordingly. For example, when you are at node 6, the maximum value is 6. However, when you go back to node 2, the maximum value is not 6 anymore, because now, 6 is not in the path. The maximum value should be 3.

Updating the `max` value on the way back is too complicated. Why don't we store the `max` value at each level? For example, when we are at node 2, we save the max value at node 2 to be 3. Then, after we go to node 6 and come back to node 2, we just get the value max that we previously saved at node 2 to update our current max.

Let's introduce `prevMax`!  
We can add one more parameter `prevMax` to our `dfs` function.  
`prevMax` is the maximum value before we call the function. Before we call the `dfs` function on the root node, `prevMax` is `-Infinity`. So, we call the `dfs` function like this: `dfs(root, -Infinity)`.

Then, inside the `dfs` function, we assign `prevMax` to `curMax`. Then, we update `curMax` depending on the value of `node.val`. Then we call `dfs` on `node.left` with the value of `curMax`. It will traverse all the way to the left, then go back. When it goes back from `node.left`, the value of `curMax` is still the same, ready for calling `dfs` on `node.right`.

So, the revised solution is like this:

```typescript
function goodNodes(root: TreeNode | null): number {
    let count = 0;

    dfs(root, -Infinity);

    return count;

    function dfs(node: TreeNode | null, prevMax: number) {
        if (node === null) return;

        let curMax = prevMax;

        if (curMax <= node.val) {
            count++;
            curMax = node.val;
        }

        dfs(node.left, curMax);
        dfs(node.right, curMax);
    }
}
```

This approach ensures that the `max` value is correctly updated as we traverse the binary tree, allowing us to accurately count the number of good nodes.