Count Good Nodes in Binary Tree

Problem Summary

• Given a tree, count all good nodes
• A good node is defined as any node that has from root to itself, no value greater than it

Approach Taken

• Keep a maxSeenSoFar, compare that against root.value
• Run Depth First Search on left and right
• Return current if good + dfs(left) + dfs(right)

Main Concepts Used

• Depth First Search
• Pre-order Traversal

Time & Space Complexity

• Time: $O(n)$ → Reason: Visiting each node
• Space: $O(h)$ → Reason: Height of the tree which can be $O(n)$ in an unbalanced tree

Code

def dfs(self, root, maxSoFar):
    if not root:
        return 0

    isGood = 1 if root.val >= maxSoFar else 0
    newMax = max(maxSoFar, root.val)

    return (
        isGood +
        self.dfs(root.left, newMax) +
        self.dfs(root.right, newMax)
    )