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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Good Nodes in Binary Tree

Difficulty: Medium

Problem Description

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.

Key Insights

  • A node is considered good if it is greater than or equal to all its ancestors in the path from the root to that node.
  • The root node is always a good node.
  • We can perform a depth-first search (DFS) or breadth-first search (BFS) to traverse the tree and keep track of the maximum value seen so far on the path to each node.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree, since we visit each node once. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack in DFS or the queue in BFS.

Solution

To solve this problem, we can use a depth-first search (DFS) approach. We'll maintain a variable to track the maximum value encountered along the path from the root to the current node. For each node, we compare its value with this maximum value. If the node's value is greater than or equal to the maximum value, it is a good node, and we increment our count. We then recursively check the left and right children of the node, updating the maximum value as we go deeper into the tree.

Code Solutions

def goodNodes(root):
    def dfs(node, max_so_far):
        if not node:
            return 0
        total_good = 1 if node.val >= max_so_far else 0
        max_so_far = max(max_so_far, node.val)
        total_good += dfs(node.left, max_so_far)
        total_good += dfs(node.right, max_so_far)
        return total_good

    return dfs(root, root.val)
← Back to All Questions