How do you solve Count Good Nodes in Binary Tree on LeetCode?

Count Good Nodes in Binary Tree (LeetCode #1448) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: The root node is always a good node.

What is the brute force solution for Count Good Nodes in Binary Tree?

The brute force approach for Count Good Nodes in Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute-force approach, we can traverse each node and check if it is good by comparing its value with all the values in the path from the root to that node. This is simple but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Count Good Nodes in Binary Tree?

Clearly explain your thought process while coding, especially how you are tracking the maximum value. Consider edge cases, such as trees with only one node or all nodes having the same value. Practice writing both the brute-force and optimal solutions to understand the trade-offs.

What are common mistakes when solving Count Good Nodes in Binary Tree?

Not keeping track of the maximum value along the path, leading to incorrect counts. Confusing the definition of good nodes and miscounting them.

#1448

Count Good Nodes in Binary Tree

Medium

TreeDepth-First SearchBreadth-First SearchBinary TreeDepth-First SearchRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

In the optimal approach, we use a depth-first search (DFS) while keeping track of the maximum value encountered along the path from the root to the current node. This allows us to determine if the current node is good without needing to check all previous nodes.

⚙️

Algorithm

4 steps

1Step 1: Initialize a DFS function that takes the current node and the maximum value from the root to this node.
2Step 2: If the current node is null, return 0.
3Step 3: Check if the current node's value is greater than or equal to the maximum value. If yes, increment the count.
4Step 4: Update the maximum value and recursively call DFS for the left and right children, summing the counts.

solution.py18 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def goodNodes(self, root: TreeNode) -> int:
10        def dfs(node, max_val):
11            if not node:
12                return 0
13            count = 1 if node.val >= max_val else 0
14            max_val = max(max_val, node.val)
15            count += dfs(node.left, max_val)
16            count += dfs(node.right, max_val)
17            return count
18        return dfs(root, root.val)

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1The root node is always a good node.
2A node is good if its value is greater than or equal to the maximum value encountered on the path from the root.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.