Leetcode - 1448. Count Good Nodes in Binary Tree

Medium

Feb 20, 2026

#binary-tree

#dfs

1448. Count Good Nodes in Binary Tree

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.

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 in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

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].

Constraints:

Notes

Intuition

Keep track of the largest node seen in the path.

Implementation

Since we are going down the path, we use DFS. Define our recursive function to the node and a max value parameter. Base case is if the root is null, return. Otherwise, check if max value is less than or equal to the current node's value (i.e. the node is larger or equal to the largest value seen before this in its path), if true, increment the good nodes counter. Call the DFS function on left and right side taking the max of the current max value and the node's value.

Time: O(n), each node is processed once
Space: O(n), call stack

Complexity

Solution

from typing import Optional
from lcutils import TreeNode

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        good_nodes = 0
        def dfs(node: Optional[TreeNode], max_val: int):
            nonlocal good_nodes
            if not node:
                return
            if max_val <= node.val:
                good_nodes += 1
            dfs(node.right, max(max_val, node.val))
            dfs(node.left, max(max_val, node.val))

        dfs(root, root.val)
        return good_nodes
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()