Skip to main content
Talentd

Count Dominant Nodes in a Binary Tree - Solution & Explanation

MediumTreeDepth-First SearchBinary Tree8 min read
Practice this problem

Problem Statement

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, 105].
  • 1 <= Node.val <= 109
  • The tree is guaranteed to be a complete binary tree.

Approach Overview

Problem Overview: You need to count how many nodes in a binary tree are dominant. A node is dominant if its value is greater than or equal to every value on the path from the root to that node. The main challenge is tracking the maximum value seen so far while traversing the tree.

Approach 1: Path Recalculation DFS (O(nh) time, O(h) space)

This brute force approach checks every node by recomputing the maximum value along the root-to-node path. You perform a DFS traversal and maintain the current path in an array or stack. For each node, iterate through the stored path to verify whether the node is dominant. This approach is useful for understanding the condition definition, but repeated path scans make it inefficient on skewed trees where height h becomes large.

Approach 2: DFS with Running Maximum (O(n) time, O(h) space)

The optimal solution uses Depth First Search and carries the maximum value seen so far during recursion. At each node, compare node.val with maxSoFar. If the current value is greater than or equal to the running maximum, increment the answer. Then recurse into the left and right subtrees with max(maxSoFar, node.val). Every node is visited exactly once, which gives linear time complexity.

This approach works naturally with recursive Binary Tree traversal because each recursive call already represents a root-to-node path. You avoid extra storage for full paths and reduce repeated comparisons. The recursion stack uses at most O(h) space, where h is the tree height.

Approach 3: Iterative DFS with Stack (O(n) time, O(h) space)

If recursion depth is a concern, you can simulate DFS using an explicit stack. Store pairs of (node, maxSoFar) while traversing the tree. Pop a node, evaluate whether it is dominant, update the running maximum, and push its children onto the stack. This iterative version avoids recursion limits and still preserves the same asymptotic complexity.

Recommended for interviews: Interviewers typically expect the DFS with running maximum approach. The brute force solution demonstrates understanding of the dominant-node condition, but the optimized DFS shows you can eliminate redundant work using state propagation during traversal. Recursive DFS is usually the cleanest implementation, while iterative DFS is preferred when stack overflow is a concern.

Solution

A node is dominant if its value equals the maximum value in the subtree rooted at it. Therefore, for each node, we only need the maximum values of its left and right subtrees, then compare them with the node itself.

Perform a bottom-up DFS: return -infty for a null node (implemented with the language's minimum integer value), and for the current node compute mx = max(leftMax, rightMax, node.val). If mx = node.val, the node is dominant and the answer is incremented by one. Finally return mx for the parent node.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Path Recalculation DFSO(nh)O(h)Useful for understanding the problem before optimization
DFS with Running MaximumO(n)O(h)Best general solution for interviews and production code
Iterative DFS with StackO(n)O(h)Preferred when recursion depth may exceed language stack limits

Video Solution

3997. Count Dominant Nodes in a Binary Tree (Leetcode Medium) • Programming Live with Larry • 78 views views

Watch 4 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Count Dominant Nodes in a 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