Skip to main content
Talentd

Count Good Nodes in Binary Tree - Solution & Explanation

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree17 min readAsked at: Amazon, Microsoft, Goldman Sachs +4
Practice this problem

Problem Statement

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

Return the number of good nodes in the binary tree.

 

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

 

Constraints:

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

Approach Overview

Problem Overview: You are given the root of a binary tree. A node is considered good if no node on the path from the root to that node has a value greater than it. The task is to count how many such nodes exist in the tree.

Approach 1: Recursive Depth First Search (DFS) (Time: O(n), Space: O(h))

Traverse the tree using DFS while carrying the maximum value seen on the path from the root to the current node. When visiting a node, compare its value with the running maximum. If node.val >= max_so_far, the node is good and you increment the count. Update the running maximum with max(max_so_far, node.val) before continuing the recursion to the left and right children. Every node is visited exactly once, giving O(n) time complexity. The recursion stack uses O(h) space where h is the tree height (worst case O(n), balanced tree O(log n)). This approach naturally fits problems involving path-based constraints in a binary tree and is the most common interview solution using depth-first search.

Approach 2: Iterative Breadth First Search (BFS) (Time: O(n), Space: O(n))

The same idea can be implemented iteratively with a queue using breadth-first search. Store pairs in the queue: the current node and the maximum value seen along the path to that node. When dequeuing, check if the node value is greater than or equal to the stored maximum. If it is, count it as a good node and update the path maximum for its children. Push each child into the queue with the updated maximum value. Since each node is processed once, the traversal runs in O(n) time. The queue may hold up to an entire level of the tree, giving O(n) auxiliary space in the worst case.

Recommended for interviews: Recursive DFS is typically expected. It directly models the path constraint by passing the current maximum down the recursion. Interviewers often want to see that you recognize the pattern of carrying state along a root-to-node path. The BFS version demonstrates the same idea iteratively and is useful if recursion depth could become an issue.

Approach 1: Recursive Depth First Search (DFS)

This approach uses a recursive depth-first search strategy, where we traverse the tree starting from the root. As we traverse, we maintain the maximum value encountered on the path from the root to the current node. A node is considered 'good' if its value is greater than or equal to the maximum value on this path. We use a recursive helper function that updates the count of good nodes accordingly.

This solution defines a helper function dfs that performs the depth-first search. It takes parameters for the current node and the maximum value encountered so far. It returns the total count of good nodes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.

Try this approach in the editor →

Approach 2: Iterative Breadth First Search (BFS)

This approach utilizes an iterative method with a queue to perform a breadth-first search (BFS) on the binary tree. As we traverse, we maintain the maximum value encountered from the root to the current node using a pair of node and max value stored in the queue. At each step, we check if the current node is a good node and update our count.

The C solution implements an iterative BFS using a custom queue structure. Each item in the queue stores a node and the maximum value along the path from the root to that node. The algorithm iterates over the queue, evaluating each node's value against the max value, updating good nodes count accordingly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Depth First Search (DFS)

Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.

Iterative Breadth First Search (BFS)

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Depth First Search (DFS)O(n)O(h)Preferred interview solution. Clean recursion and natural for path-based tree problems.
Iterative Breadth First Search (BFS)O(n)O(n)Useful when avoiding recursion or when processing nodes level by level.

Video Solution

Microsoft's Most Asked Question 2021 - Count Good Nodes in a Binary Tree - Leetcode 1448 - Python • NeetCode • 149,763 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Good Nodes in Binary Tree easy or hard?
The problem is rated Medium because it requires recognizing a path-based condition during tree traversal. Once you realize you must carry the maximum value along the root-to-node path, the implementation using DFS or BFS becomes straightforward.
Count Good Nodes in Binary Tree Python/Java solution
In both Python and Java, the typical solution uses DFS recursion with a parameter representing the maximum value seen so far. Each recursive call checks the current node against this maximum and updates it before exploring children. The logic is identical across languages and runs in O(n) time.
How to solve Count Good Nodes in Binary Tree in O(n)?
Traverse the tree while maintaining the maximum value seen on the path from the root to the current node. During DFS or BFS, compare the current node value with this maximum. If it is greater than or equal, increment the good node count and update the maximum before continuing traversal. Since each node is processed once, the algorithm runs in O(n) time.
What is the best approach for Count Good Nodes in Binary Tree?
Recursive Depth First Search (DFS) is the most common approach. Track the maximum value seen along the path from the root to the current node and compare it with the current node value. If the node value is greater than or equal to the maximum so far, it is counted as a good node. The traversal visits each node once, giving O(n) time complexity.
Is Count Good Nodes in Binary Tree asked at Google/Amazon/Meta?
Tree traversal and path constraint problems like this frequently appear in interviews at large tech companies including Amazon, Google, and Meta. Variations that involve tracking values along root-to-node paths are common in technical screening rounds.
What data structure is used in Count Good Nodes in Binary Tree?
The core data structure is a binary tree. The algorithm typically uses recursion with the call stack for DFS or a queue for BFS traversal while storing the current node and the maximum value seen along its path.
What is the time complexity of Count Good Nodes in Binary Tree?
The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during traversal. Space complexity is O(h) for recursive DFS due to the recursion stack, where h is the tree height, or O(n) when using an iterative BFS queue.

Ready to solve this problem?

Practice Count Good Nodes in Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II