Medium — Binary Tree | Depth-First Search | Recursion | Tree Traversal

The Problem

Count the number of ‘good’ nodes in a binary tree, where a node is considered good if there are no nodes with a value greater than it in the path from root to that node.

Approach

Use depth-first search (DFS) to traverse the tree while keeping track of the maximum value seen along the current path. For each node, check if its value is greater than or equal to the current maximum to determine if it’s a good node.

Time: O(n) · Space: O(h)

Code

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_val):
            if not node:
                return 0

            if node.val >= max_val:
                max_val = node.val
                count = 1
            else:
                count = 0

            count += dfs(node.left, max_val)
            count += dfs(node.right, max_val)

            return count

        return dfs(root, float("-inf"))

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment