← Trees

Drill #141 — Count Good Nodes in Binary Tree

Medium DFS with Max Trees

In plain English: Count nodes where no ancestor on the path from the root has a larger value.

DFS passing the maximum value seen so far on the path from root. A node is good if its value >= max_so_far. Update max_so_far as you recurse deeper.

Prompt

Given a binary tree root, a node X is 'good' if there are no nodes with a greater value on the path from root to X. Return the number of good nodes.

Try to write it from scratch before scrolling down.

Solution

def good_nodes(root):
    def dfs(node, max_so_far):
        if not node:
            return 0
        # node is "good" when no ancestor on root-to-node path had a larger value
        good = 1 if node.val >= max_so_far else 0
        new_max = max(max_so_far, node.val)  # propagate tighter bound to children
        return good + dfs(node.left, new_max) + dfs(node.right, new_max)
    return dfs(root, root.val)

# Test: tree [3,1,4,3,null,1,5]
# good nodes: 3 (root), 4, 3 (left-left), 5 => count = 4
O(n) time · O(h) space (recursion depth)

Related Micro Drills

← Drill #140