Is Count Dominant Nodes in a Binary Tree easy or hard?

Count Dominant Nodes in a Binary Tree is generally considered a medium-level problem. The traversal itself is straightforward, but candidates often struggle with maintaining path-specific state efficiently without recomputing values repeatedly.

Count Dominant Nodes in a Binary Tree Python/Java solution

Python solutions typically use recursive DFS with a helper function carrying maxSoFar as a parameter. Java implementations follow the same idea using class methods and integer tracking. Both versions achieve O(n) time complexity and O(h) space complexity.

How to solve Count Dominant Nodes in a Binary Tree in O(n)?

Use depth-first traversal while carrying the maximum value encountered on the current root-to-node path. At each node, compare the node value with the running maximum and update the answer if the condition is satisfied. Pass the updated maximum to child nodes so every node is processed in constant time.

What is the best approach for Count Dominant Nodes in a Binary Tree?

The best approach is DFS with a running maximum value. During traversal, track the maximum node value seen from the root to the current node. If the current node value is greater than or equal to that maximum, count it as dominant. This solution runs in O(n) time with O(h) recursion stack space.

Is Count Dominant Nodes in a Binary Tree asked at Google/Amazon/Meta?

Binary tree DFS problems with path-state tracking are common in interviews at Google, Amazon, and Meta. Variants of this problem frequently appear under names like Good Nodes in Binary Tree or Visible Nodes. Interviewers use it to evaluate recursion, tree traversal, and state propagation skills.

What data structure is used in Count Dominant Nodes in a Binary Tree?

The primary data structure is a binary tree combined with DFS traversal. Recursive solutions use the call stack implicitly, while iterative implementations use an explicit stack storing pairs of node references and running maximum values.

What is the time complexity of Count Dominant Nodes in a Binary Tree?

The optimal DFS solution runs in O(n) time because each node is visited exactly once. The auxiliary space complexity is O(h), where h is the height of the binary tree due to recursion or an explicit stack.

Description Hints 3 Solution Video 5:23

3997. Count Dominant Nodes in a Binary Tree

Medium72.1% acceptance

You are given the root of a complete binary tree.

A node x is called dominant if its value is equal to the maximum value among all nodes in the subtree rooted at x.

Return the number of dominant nodes in the tree.

Example 1:

Input: root = [5,3,8,2,4,7,1]

Output: 5

Explanation:

The leaf nodes with values 2, 4, 7, and 1 are dominant.
The node with value 8 is dominant because its value is the maximum value in its subtree [8, 7, 1].
Thus, the answer is 5.

Example 2:

Input: root = [1,2,3,1,2]

Output: 4

Explanation:

The leaf nodes with values 1, 2, and 3 are dominant.
The node with value 2 whose subtree is [2, 1, 2] is dominant because its value is the maximum value in its subtree.
Thus, the answer is 4.

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁹
The tree is guaranteed to be a complete binary tree.

Topics

Hints open one at a time

Hint 1

Process the tree using postorder traversal, so both child subtrees are handled before their parent.

Hint 2

For each node, compute the maximum value in its subtree from its own value and the maximum values returned by its children.

Hint 3

A node is dominant if its value is equal to this subtree maximum.

5:23

Still stuck?Read the written solution, 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 countDominantNodes(self, root: TreeNode | None) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[5,3,8,2,4,7,1]

Input

[1,2,3,1,2]

Your code is saved on this device.Solution