Count Dominant Nodes in a Binary Tree - Video Solutions
3997. Count Dominant Nodes in a Binary Tree (Leetcode Medium)
Count Dominant Nodes in a Binary Tree - Video Solution
Watch 5 video solutions for Count Dominant Nodes in a Binary Tree, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by Programming Live with Larry has 78 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |