Count Good Nodes in Binary Tree

📋

Problem

Imagine you are analyzing a network of sensors arranged in a tree structure, and you want to count how many sensors have readings that are the highest seen so far on the path from the root sensor.

Given a binary tree where each node contains an integer value, 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's value. Return the number of good nodes in the binary tree.

The number of nodes in the binary tree is in the range [1, 10^5].Each node's value is an integer in the range [-10^4, 10^4].

Edge cases: Single node tree → output is 1All nodes have the same value → output equals total nodesStrictly decreasing values from root → output is 1

</>

IDE

def count_good_nodes(root: Optional[TreeNode]) -> int:public int countGoodNodes(TreeNode root)int countGoodNodes(TreeNode* root)function countGoodNodes(root)

def count_good_nodes(root):
    # Write your solution here
    pass

class Solution {
    public int countGoodNodes(TreeNode root) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countGoodNodes(TreeNode* root) {
    // Write your solution here
    return 0;
}

function countGoodNodes(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 3Not counting nodes equal to max value on path as good nodes.✅ Change comparison from > to >= when checking if node.val is good.

Wrong: 7Counting nodes greater than parent only, ignoring ancestors (greedy bug).✅ Track max value from root to current node, not just parent node.

Wrong: 0Missing base case for single node tree or null root.✅ Return 1 for non-null root node as it is always good.

Wrong: 8Double counting nodes due to revisiting or incorrect traversal.✅ Traverse tree once with DFS/BFS and count nodes only once.

Wrong: TLEUsing exponential or repeated traversals instead of O(n) traversal.✅ Implement O(n) DFS or BFS with max value tracking.

✓

Test Cases

Try testing your solution on minimal and boundary inputs to catch base case bugs.

Consider tricky cases that expose greedy or off-by-one errors in your max tracking logic.

Prepare for large inputs by ensuring your solution runs in linear time and uses efficient traversal.

t1_01basic

Input{"root":[3,1,4,3,null,1,5]}

Expected4

⏱ Performance - must finish in 2000ms

The good nodes are 3 (root), 4, 5, and the left child 3 of node 1. Each of these nodes is greater than or equal to all nodes on the path from the root.

💡 Think about tracking the maximum value seen so far on the path from root to current node.

💡 Use DFS or BFS to traverse the tree while passing down the max value encountered.

💡 Count a node as good if its value is >= max value on the path; update max accordingly.

Why it failed: Incorrect count likely due to not updating or comparing max value correctly on the path. Fix by passing max_val parameter and updating it with max(max_val, node.val) during traversal.

✓ Correctly counts good nodes by tracking max value on path.

t1_02basic

Input{"root":[2,2,2]}

Expected3

⏱ Performance - must finish in 2000ms

All nodes have the same value 2, so all are good nodes since no node on the path is greater than any node.

💡 Consider how equality affects the 'good node' condition.

💡 Check if your comparison uses >= instead of > when comparing node values.

💡 Ensure nodes with values equal to max on path are counted as good.

Why it failed: Failing to count nodes equal to max value on path causes undercount. Fix by using >= comparison instead of > when checking node values.

✓ Correctly counts nodes equal to max value as good.

t2_01edge

Input{"root":[10]}

Expected1

⏱ Performance - must finish in 2000ms

Single node tree; the root itself is always a good node.

💡 Check how your code handles trees with only one node.

💡 Make sure base case returns 1 for non-null node.

💡 Confirm that root node is counted as good regardless of value.

Why it failed: Code returns 0 for single node tree due to missing base case. Fix by returning 1 when node is not null and no parent max exists.

✓ Correctly counts single node as good.

t2_02edge

Input{"root":[5,4,null,3,null,2,null,1]}

Expected1

⏱ Performance - must finish in 2000ms

Strictly decreasing values from root; only root node is good.

💡 Consider how max value on path affects nodes with decreasing values.

💡 Check if your code incorrectly counts nodes smaller than max as good.

💡 Ensure only nodes >= max on path are counted.

Why it failed: Counting nodes smaller than max value on path causes overcount. Fix by comparing node.val >= max_val before counting.

✓ Correctly counts only root as good in decreasing value tree.

t2_03edge

Input{"root":[0,-1,-1,-2,-3,-4,-5]}

Expected1

⏱ Performance - must finish in 2000ms

Tree with negative values; only root node 0 is good as all others are smaller.

💡 Verify your code handles negative values correctly.

💡 Check if max value tracking works with negative integers.

💡 Ensure comparison logic is consistent regardless of sign.

Why it failed: Failing to handle negative values causes incorrect counts. Fix by using max_val initialized to root.val and comparing node.val >= max_val properly.

✓ Correctly counts good nodes with negative values.

t3_01corner

Input{"root":[1,2,3,4,5,6,7]}

Expected7

⏱ Performance - must finish in 2000ms

All nodes have increasing values on all paths; all nodes are good.

💡 Beware of greedy approaches that only check immediate parent.

💡 Remember max value must be tracked from root to current node, not just parent.

💡 Fix by passing max_val parameter through entire path, not resetting at each node.

Why it failed: Greedy bug: counting node as good if greater than parent only, ignoring ancestors. Fix by tracking max value from root to current node, not just parent.

✓ Correctly tracks max value along entire path, not just parent.

t3_02corner

Input{"root":[3,3,3,3,3,3,3]}

Expected7

⏱ Performance - must finish in 2000ms

All nodes have identical values; all nodes are good.

💡 Check if your code mistakenly excludes nodes equal to max value.

💡 Confirm comparison uses >= not > for counting good nodes.

💡 Fix by changing comparison operator to >=.

Why it failed: Off-by-one bug: using > instead of >= excludes equal nodes. Fix by using node.val >= max_val in condition.

✓ Correctly counts nodes equal to max value as good.

t3_03corner

Input{"root":[5,1,6,null,2,null,7]}

Expected4

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 and unbounded knapsack style problems: each node counted once, no repeats.

💡 Ensure each node is counted once, no double counting.

💡 Avoid counting nodes multiple times by revisiting paths.

💡 Fix by traversing tree once and counting nodes based on path max.

Why it failed: Double counting bug: counting nodes multiple times due to revisiting or incorrect traversal. Fix by single DFS/BFS traversal with max tracking.

✓ Correctly counts each node once with proper traversal.

t4_01performance

Input{"root":[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]}

Expectednull

⏱ Performance - must finish in 2000ms

Large tree with 127 nodes (complete binary tree of height 6) with all zero values; O(n) solution must complete within 2 seconds.

💡 Focus on O(n) time complexity traversal.

💡 Avoid recursive stack overflow by using iterative BFS or DFS if needed.

💡 Use efficient max tracking without recomputing for each node.

Why it failed: TLE caused by exponential or repeated traversals. Fix by using O(n) BFS or DFS with max value tracking.

✓ Solution runs in O(n) time confirming efficiency.

Practice

1. Consider the following code snippet for computing average values of each level in a binary tree. Given the tree with root value 3, left child 9, and right child 20 with children 15 and 7, what is the value of level_sum during the second iteration of the while loop (processing the second level)?

easy

A. 29

B. 14.5

C. 9

D. 20

Solution

1. Step 1: Trace first iteration of while loop

   Queue starts with [3]. level_count=1, level_sum=3. After processing, queue becomes [9,20].

2. Step 2: Trace second iteration of while loop

   Queue now [9,20], level_count=2. level_sum = 9 + 20 = 29. Then children 15 and 7 are added to queue.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of nodes at second level is 9 + 20 = 29 [OK]

Hint: Sum nodes at current queue size before adding children [OK]

Common Mistakes:

• Confusing level_sum with average
• Using previous level's sum
• Off-by-one in loop iteration

2. You are given a binary tree and need to find the maximum width among all levels. The width is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), including null nodes in between. Which approach guarantees an optimal solution for this problem?

easy

A. Use BFS with indexing of nodes to track their positions and normalize indices at each level to avoid overflow.

B. Perform a simple level order traversal counting only non-null nodes at each level and take the maximum count.

C. Use DFS to traverse the tree and track the minimum and maximum node indices at each depth to compute width.

D. Apply a greedy approach that always picks the widest subtree at each node to estimate maximum width.

Solution

1. Step 1: Understand the problem constraints

   The width includes null nodes between end-nodes, so counting only non-null nodes per level underestimates width.

2. Step 2: Identify the approach that tracks positions

   BFS with indexing assigns position indices to nodes, allowing calculation of width as the difference between first and last indices at each level. Normalizing indices prevents integer overflow on deep trees.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Indexing with normalization handles sparse trees and deep levels correctly [OK]

Hint: Index nodes with BFS and normalize indices [OK]

Common Mistakes:

• Counting only non-null nodes per level
• Using DFS without proper indexing
• Ignoring index normalization causing overflow

3. Given the following code snippet implementing the optimal approach to connect next right pointers in a perfect binary tree, what is the value of root.left.next.val after calling connect(root) on the tree Node(1, Node(2), Node(3))?

easy

A. None

B. 2

C. 3

D. 1

Solution

1. Step 1: Trace the first iteration of the outer while loop

   leftmost is root (1), which has left child (2). Inside inner loop, head is 1, so 2.next = 3.

2. Step 2: Check the value of root.left.next

   root.left is node 2, its next pointer is set to node 3, so root.left.next.val = 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   2.next points to 3 after connect [OK]

Hint: Next pointer of left child points to right sibling [OK]

Common Mistakes:

• Confusing node values
• Assuming next is None by default
• Mixing up left and right children

4. You are given a binary tree and need to determine if it is symmetric around its center. Which approach best guarantees an optimal solution by comparing nodes in pairs using a queue and terminating early when asymmetry is detected?

easy

A. Recursive depth-first traversal comparing left subtree to left subtree

B. Dynamic programming storing subtree symmetry states bottom-up

C. Greedy traversal checking only the root and immediate children

D. Iterative breadth-first search using a queue to compare mirrored node pairs with early termination

Solution

1. Step 1: Understand the problem requirement

   The problem requires checking if a tree is symmetric, which means the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes efficiently

   Using an iterative BFS with a queue to compare pairs of nodes from left and right subtrees simultaneously allows early detection of asymmetry and avoids unnecessary traversal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Iterative BFS with paired nodes and early termination is optimal for symmetry check [OK]

Hint: Symmetry requires mirrored node pair comparison [OK]

Common Mistakes:

• Comparing left subtree to left subtree instead of mirrored right subtree
• Using greedy checks that miss deeper asymmetry
• Assuming symmetry can be checked by root and immediate children only

5. What is the time complexity of the optimal BFS approach that finds the bottom-left value by inserting the right child before the left child in the queue for a binary tree with n nodes and maximum width w?

medium

A. O(n log n) due to repeated queue operations

B. O(n^2) in worst case when tree is skewed

C. O(w * n) because each level's width multiplies the number of nodes processed

D. O(n) because each node is enqueued and dequeued exactly once

Solution

1. Step 1: Identify number of operations per node

   Each node is enqueued once and dequeued once, so total queue operations are proportional to n.

2. Step 2: Analyze complexity

   Queue operations (append, popleft) are O(1), so total time is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each node processed once -> O(n) time [OK]

Hint: Each node visited once in BFS -> O(n) time [OK]

Common Mistakes:

• Confusing width w as multiplicative factor in time
• Assuming queue operations cost more than O(1)
• Thinking skewed trees cause quadratic time