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.

Description Hints 1 Solution Video 8:18

1448. Count Good Nodes in Binary Tree

Medium73.8% acceptance7 companies

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].

Asked at 7 companies

Josh Technology DocuSign Microsoft Goldman Sachs

Google Amazon Meta

Topics

Hints open one at a time

Hint 1

Use DFS (Depth First Search) to traverse the tree, and constantly keep track of the current path maximum.

8:18

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def goodNodes(self, root: TreeNode) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,1,4,3,null,1,5]

Input

[3,3,null,4,2]

Input

[1]

Your code is saved on this device.Solution