Count Dominant Nodes in a Binary Tree - Solution & Explanation

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.