Count Good Nodes in Binary Tree

Problem Statement

Within a binary tree, a node x is considered good if the path from the root of the tree to the node x contains no nodes with a value greater than the value of node x

Given the root of a binary tree root, return the number of good nodes within the tree.

Example 1:

# Input: root = [2,1,1,3,null,1,5]
# Output: 3

Example 2:

# Input: root = [1,2,-1,3,4]
# Output: 4

Constraints:

  • 1 <= number of nodes in the tree <= 100
  • -100 <= Node.val <= 100

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

Hint 1

A brute force solution would involve considering every node and checking if the path from the root to that node is valid, resulting in an O(n^2) time complexity. Can you think of a better approach?

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse the tree. But can you think of a way to determine if the current node is a good node in a single traversal? Maybe we need to track a value while traversing the tree.

Hint 3

While traversing the tree, we should track the maximum value along the current path. This allows us to determine whether the nodes we encounter are good. We can use a global variable to count the number of good nodes.

Solution

from collections import deque


# 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




def good_nodes(root: TreeNode) -> int:
    """Counts the number of "good" nodes in a binary tree using DFS.


    A node is considered "good" if no node on the path from the root to it
    has a value greater than it.
    """


    def dfs(node, max_val):
        if not node:
            return 0


        res = 1 if node.val >= max_val else 0
        max_val = max(max_val, node.val)
        res += dfs(node.left, max_val)
        res += dfs(node.right, max_val)
        return res


    return dfs(root, root.val)

Time complexity: O(n) Space complexity: O(n)

from collections import deque




# 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




def good_nodes(root: TreeNode) -> int:
    """Counts the number of "good" nodes in a binary tree using BFS.


    A node is considered "good" if no node on the path from the root to it
    has a value greater than it.
    """
    res = 0
    q = deque()


    q.append((root, float('-inf')))


    while q:
        node, max_val = q.popleft()
        if node.val >= max_val:
            res += 1


        if node.left:
            q.append((node.left, max(max_val, node.val)))


        if node.right:
            q.append((node.right, max(max_val, node.val)))


    return res

Time complexity: O(n) Space complexity: O(n)