Good Nodes in a Binary Tree

Problem Description

Given a binary tree root, a node X in the tree is named good if in the path from the root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Naive Approach

A brute-force approach would involve traversing each path from the root to every node and checking if the current node is good based on the nodes encountered along the way.

1. Start at the root.
2. For each node, traverse the path from the root to that node.
3. Keep track of the maximum value encountered along the path.
4. If the current node's value is greater than or equal to the maximum value, increment the good node count.

Big O Runtime: O(NlogN) in balanced tree or O(N^2) in skewed tree, where N is the number of nodes. This is because, in the worst case, for each node, we might have to traverse a path of length N.

Big O Space: O(H), where H is the height of the tree. This is due to the recursive call stack.

Optimal Approach

A more efficient approach involves a Depth-First Search (DFS) while carrying the maximum value seen so far in the path from the root.

1. Initialize a count of good nodes to 0.
2. Start a DFS traversal from the root.
3. At each node, check if its value is greater than or equal to the maximum value seen so far.
   • If it is, increment the good node count and update the maximum value.
4. Recursively traverse the left and right subtrees, passing the updated maximum value.

Big O Runtime: O(N), where N is the number of nodes in the tree, as each node is visited exactly once.

Big O Space: O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H can be equal to N.

Edge Cases

• Empty Tree: If the root is null, the number of good nodes is 0.
• Single Node Tree: If the tree contains only the root, the root is always a good node, so return 1.
• Nodes with Same Value: If multiple nodes have the same value along a path, the lower nodes are still considered "good" if their value is greater than or equal to the maximum value encountered so far.

Code (Python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


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

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

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

            return count

        return dfs(root, root.val)