Count Good Nodes in Binary Tree

Count Good Nodes in Binary Tree

What is this problem about?

In the Count Good Nodes in Binary Tree interview question, a node X in a binary tree is considered "good" if on the path from the root to X, there are no nodes with a value greater than X. You need to return the total number of good nodes in the tree.

Why is this asked in interviews?

Microsoft and Meta use the Depth-First Search interview pattern for this problem to evaluate your understanding of state propagation in tree traversals. It’s a "Medium" difficulty task that tests if you can pass information (the maximum value seen so far) down the recursion stack. It demonstrates a fundamental recursive thinking pattern.

Algorithmic pattern used

This problem is solved using Depth-First Search (DFS).

1. Start at the root. The root is always a good node.
2. Pass the max_so_far value to the recursive calls for the children.
3. For a child node:
   • If child.val >= max_so_far, the child is "good". Increment count.
   • Update max_so_far = max(max_so_far, child.val).
4. Recurse for left and right subtrees.

Example explanation

Tree: [3, 1, 4, 3, null, 1, 5]

1. Root 3: Good. max=3.
2. Left 1: 1 < 3. Not good. max=3.
3. Left-Left 3: 3 >= 3. Good. max=3.
4. Right 4: 4 >= 3. Good. max=4.
5. Right-Left 1: 1 < 4. Not good.
6. Right-Right 5: 5 >= 4. Good. Total Good Nodes: 4.

Common mistakes candidates make

• Not updating Max: Forgetting to update the max_so_far variable as you go deeper, leading to incorrect "good" classifications.
• Global Variable issues: Using a global variable for max_so_far that doesn't reset correctly when the recursion backtracks. It must be passed as a parameter.
• Base Case: Not handling null nodes gracefully.

Interview preparation tip

Tree problems that depend on the path from the root are perfect candidates for DFS where you pass a "state" variable (like sum, max, or min) as a parameter.