Count Dominant Nodes in a Binary Tree
In many hierarchical systems, like Postman's collection or environment variables, properties can be inherited or overridden. Imagine a binary tree where each node represents a configuration setting, and its value is a numerical priority. A configuration is 'dominant' if its priority is at least as high as any configuration on the path from the root to its immediate parent. Understanding how many such dominant configurations exist can be crucial for performance optimization or access control analysis.
Your task is to count the total number of 'dominant' nodes in a given binary tree.
Implement the function countDominantNodes which takes the root of a binary tree and returns the total count of dominant nodes within it.
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 {
// your code here
}
root: TreeNode | null
TreeNode has a val (number), left (TreeNode or null), and right (TreeNode or null).number
x is dominant if its val is greater than or equal to the maximum val encountered on the path from the root to x's immediate parent. The root node is always considered dominant (as it has no parent, and thus no prior maximum to beat).root is null, the function should return 0.node.val >= max_so_far correctly handles this.Examples
Example 1
Input:
root = [3,1,4,3,null,1,5]
Output:
4
Note:
The dominant nodes are:
Example 2
Input:
root = [3,null,4,null,5,null,6]
Output:
4
Note:
All nodes in this skewed tree are dominant: 3, 4, 5, 6. Each node's value is greater than or equal to the maximum value on the path to its parent.
Example 3
Input:
root = [1,2,3]
Output:
3
Note:
The dominant nodes are:
Example 4
Input:
root = []
Output:
0
Note:
An empty tree has no nodes, thus no dominant nodes.
Constraints
0 and 10^5.val) are between -10^4 and 10^4.Loading editor...