#55 Medium Time O(n) Space O(n) Animated

Count Good Nodes in Binary Tree

Count nodes where path from root has no greater value.

LeetCode ↗

Approach: DFS (Pre-order)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Count nodes where path from root has no greater value.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — DFS (Pre-order)

O(n) O(n)

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

Binary Tree Right Side View

Validate Binary Search Tree

Count Good Nodes in Binary Tree

Steps

Description

Constraints

Tags

Solution — DFS (Pre-order)