We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Good Nodes in Binary Tree

Number: 1544

Difficulty: Medium

Paid? No

Companies: Meta, josh technology, Google, Docusign, Goldman Sachs, Microsoft

Problem Description

Given a binary tree, a node X is considered good if on the path from the root to X there are no nodes with a value greater than X. The task is to count the number of good nodes in the binary tree.

Key Insights

  • Perform a tree traversal (DFS or BFS) from the root.
  • Keep track of the maximum value encountered along the current path.
  • A node is "good" if its value is greater than or equal to the maximum value seen so far.
  • Update the maximum value as you traverse deeper in the tree.
  • The root is always a good node.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited exactly once. Space Complexity: O(h), where h is the height of the tree (O(n) in the worst-case of a skewed tree).

Solution

We can solve this problem using Depth-First Search (DFS) recursion. Starting from the root, we pass along the current maximum value encountered on the path. For each node, we check if its value is greater than or equal to this maximum. If it is, we count it as a good node and update the maximum value if necessary. This process is continued recursively for both the left and right children of the node. Finally, we sum the counts from both subtrees.

Code Solutions

# 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:
        # Helper function to perform DFS traversal.
        def dfs(node, currentMax):
            # If we reach a null node, there are no further nodes to count.
            if not node:
                return 0
            
            # Check if current node is good.
            count = 1 if node.val >= currentMax else 0
            # Update the current maximum value.
            newMax = max(currentMax, node.val)
            
            # Recursively count good nodes in the left and right subtrees.
            count += dfs(node.left, newMax)
            count += dfs(node.right, newMax)
            return count
        
        # Start DFS traversal from root with initial maximum value as root's value.
        return dfs(root, root.val)
← Back to All Questions