Count Good Nodes in a Binary Tree

Interview Problem Interview Medium Binary Tree Depth-first Search Recursion

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.goodNodes(root). A node is good when no earlier node on its root-to-node path has a greater value. Return the count of good nodes.

Starter code

class Solution:
    def goodNodes(self, root):
        pass

Test cases

sample

{
  "args": [
    {
      "$type": "binary-tree",
      "values": [
        3,
        1,
        4,
        3,
        null,
        1,
        5
      ]
    }
  ]
}

Expected: 4

Wizard outline

Step 1: Initialize Solution.goodNodes
Replace the empty starter with the first real state owned by Solution.goodNodes. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Single case
Complete the readable core algorithm for one representative Interview case. Compare each value with its path maximum, then propagate the updated maximum independently to children.
Step 3: Harden the Equal Is Good boundary
Repair the reviewed boundary and pass the complete submission contract. The carried maximum is exactly the greatest ancestor value on the current path. The comparison therefore matches the good-node definition, and updating it preserves the invariant for both child paths.

Footguns and prerequisites

The comparison is >=, so a value equal to the path maximum is still good.
trees and graphs

Reviewed references

LeetCode 1448 — Count Good Nodes in Binary Tree

Practice prerequisites

Carry State Through Tree DFS(opens in a new tab)
Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing count good tree nodes as a complete Interview Problem.

Recommended approach and implementation

DFS with the maximum value encountered before the node. Count node when value>=maximum and recurse with max(maximum,value).

Why it works: The carried maximum is exactly the greatest ancestor value on the current path. The comparison therefore matches the good-node definition, and updating it preserves the invariant for both child paths.

class Solution:
    def goodNodes(self, root):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        def count(node, maximum):
            if node is None: return 0
            good = 1 if node.val >= maximum else 0
            updated = max(maximum, node.val)
            return good + count(node.left, updated) + count(node.right, updated)
        return count(root, float('-inf'))