1448. Count Good Nodes in Binary Tree

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:

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:

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:

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.

• 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:

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.