Count Good Nodes in Binary Tree

1. The obvious way

   For each node walk back up to the root checking its ancestors: O(n x height).

2. The key insight

   Carry down the largest value seen on the path. If the current node's value is at least that largest, it is good: count it. The new largest for the children is the bigger of the two. One visit per node.

3. The algorithm
   1. Start at the root with the largest so far = negative infinity.
   2. Node value >= largest so far? It is good: count 1.
   3. New largest = max(largest, node value).
   4. Add the good counts of the left and right subtrees.

Watch it run

good: 1

def good_nodes(root):
    def count(node, highest):
        if node is None:
            return 0
        good = 1 if node.val >= highest else 0          # no one on the path is higher
        highest = max(highest, node.val)
        return good + count(node.left, highest) + count(node.right, highest)

    return count(root, float("-inf"))

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.