Count Good Nodes in Binary Tree

Difficulty: Medium Source: NeetCode

Problem

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

Example 1: Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: Nodes 3 (root), 4, 3 (left-left), and 5 are good.

Example 2: Input: root = [3,3,null,4,2] Output: 3

Constraints:

The number of nodes in the binary tree is in the range [1, 10^5]

Each node’s value is between [-10^4, 10^4]

Prerequisites

Before attempting this problem, you should be comfortable with:

DFS with State — Passing extra information (max seen so far) down the recursion
Path Properties — Understanding that a condition depends on the entire root-to-node path
Preorder DFS — Processing the current node before its children

1. DFS (Preorder, Passing Max)

A node is “good” if its value is greater than or equal to every value on the path from the root to it. Equivalently, it’s good if its value >= the maximum value seen so far on the path. We can track this max as we go down the tree. At each node, check if node.val >= max_so_far, then update the max and recurse.

Algorithm

Define DFS with parameters (node, max_so_far)
If node is null, return 0
Count this node as good if node.val >= max_so_far
Update new_max = max(max_so_far, node.val)
Return is_good + dfs(left, new_max) + dfs(right, new_max)

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def good_nodes(root):
    def dfs(node, max_so_far):
        if not node:
            return 0

        # This node is good if its value >= max value on the path from root
        is_good = 1 if node.val >= max_so_far else 0

        # Update the running max for children
        new_max = max(max_so_far, node.val)

        return is_good + dfs(node.left, new_max) + dfs(node.right, new_max)

    # Start with -infinity so the root always counts as good
    return dfs(root, float('-inf'))

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
# Tree: [3,1,4,3,null,1,5]
#         3
#        / \
#       1   4
#      /   / \
#     3   1   5
root1 = build_tree([3, 1, 4, 3, None, 1, 5])
print(good_nodes(root1))  # 4 (nodes: 3, 4, 3, 5)

# Tree: [3,3,null,4,2]
#       3
#      /
#     3
#    / \
#   4   2
root2 = build_tree([3, 3, None, 4, 2])
print(good_nodes(root2))  # 3 (nodes: 3, 3, 4)

root3 = build_tree([1])
print(good_nodes(root3))  # 1

# All negative values
root4 = build_tree([-1, -2, -3])
print(good_nodes(root4))  # 1 (only root is good: -1 >= -inf; -2 < -1; -3 < -1)

Complexity

Time: O(n) — every node is visited exactly once
Space: O(h) — recursion stack depth equals tree height

2. Iterative DFS (Stack with State)

Intuition

Same idea as the recursive version but we manage the stack explicitly. Push tuples of (node, max_so_far) onto the stack.

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def good_nodes_iterative(root):
    if not root:
        return 0

    count = 0
    stack = [(root, float('-inf'))]

    while stack:
        node, max_so_far = stack.pop()

        if node.val >= max_so_far:
            count += 1

        new_max = max(max_so_far, node.val)

        if node.left:
            stack.append((node.left, new_max))
        if node.right:
            stack.append((node.right, new_max))

    return count

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 1, 4, 3, None, 1, 5])
print(good_nodes_iterative(root1))  # 4

root2 = build_tree([3, 3, None, 4, 2])
print(good_nodes_iterative(root2))  # 3

Complexity

Time: O(n) — every node processed once
Space: O(h) — stack size

Common Pitfalls

Starting max_so_far at 0. If tree values are all negative, initializing to 0 would incorrectly mark the root as not good. Always initialize to float('-inf') so the root is always counted.

Checking node.val > max_so_far instead of >=. The problem says “no node with a value strictly greater than X” on the path — so a node is good if its value is >= the running max. A tie (equal value) still counts as good.

Keyboard shortcuts

Note Book