Count Dominant Nodes in a Binary Tree solution and explanation
4 more videos on this problem
3997. Count Dominant Nodes in a Binary Tree (Leetcode Medium)Programming Live with Larry · 5:23 · 78 views
LeetCode 3997 | Count Dominant Nodes in a Binary Tree | Postorder DFS | JavaCode Kage · 8:45 · 74 views
Leetcode contest 511 - 3997 - Count Dominant Nodes in a Binary TreeManjeet Dhayal · 3:51 · 37 views
Leetcode 3997. Count Dominant Nodes in a Binary Tree | DFS | Tree | MediumLeet's Code · 20:49 · 31 views
Count Dominant Nodes in a Binary Tree ( LeetCode 3997 C++ )AeXel · 8:56 · 28 views
The problem
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.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countDominantNodes(self, root: TreeNode | None) -> int:
def dfs(node: TreeNode | None) -> int:
if node is None:
return -inf
l = dfs(node.left)
r = dfs(node.right)
mx = max(l, r, node.val)
if mx == node.val:
nonlocal ans
ans += 1
return mx
ans = 0
dfs(root)
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
public int countDominantNodes(TreeNode root) {
dfs(root);
return ans;
}
private int dfs(TreeNode node) {
if (node == null) {
return Integer.MIN_VALUE;
}
int l = dfs(node.left);
int r = dfs(node.right);
int mx = Math.max(Math.max(l, r), node.val);
if (mx == node.val) {
++ans;
}
return mx;
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countDominantNodes(TreeNode* root) {
int ans = 0;
auto dfs = [&](this auto&& dfs, TreeNode* node) -> int {
if (!node) {
return INT_MIN;
}
int l = dfs(node->left);
int r = dfs(node->right);
int mx = max({l, r, node->val});
if (mx == node->val) {
++ans;
}
return mx;
};
dfs(root);
return ans;
}
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function countDominantNodes(root: TreeNode | null): number {
let ans = 0;
const dfs = (node: TreeNode | null): number => {
if (!node) {
return -Infinity;
}
const l = dfs(node.left);
const r = dfs(node.right);
const mx = Math.max(l, r, node.val);
if (mx === node.val) {
++ans;
}
return mx;
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countDominantNodes(root *TreeNode) int {
ans := 0
var dfs func(*TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return math.MinInt32
}
l := dfs(node.Left)
r := dfs(node.Right)
mx := max(l, r, node.Val)
if mx == node.Val {
ans++
}
return mx
}
dfs(root)
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Path Recalculation DFS | O(nh) | O(h) | Useful for understanding the problem before optimization |
| DFS with Running Maximum | O(n) | O(h) | Best general solution for interviews and production code |
| Iterative DFS with Stack | O(n) | O(h) | Preferred when recursion depth may exceed language stack limits |
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.