Frontend School

Count Dominant Nodes in a Binary Tree

DSA
medium

Count Dominant Nodes in a Binary Tree

Medium
Tree
DFS
Binary Tree

Overview

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.

What you need to do / Task

Implement the function countDominantNodes which takes the root of a binary tree and returns the total count of dominant nodes within it.

Input & output

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
}
  • Input: root: TreeNode | null
    • The root of a binary tree. Each TreeNode has a val (number), left (TreeNode or null), and right (TreeNode or null).
  • Output: number
    • The total count of dominant nodes in the tree.

Clarifications

  • What is a 'dominant' node? A node 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).
  • Empty tree? If the root is null, the function should return 0.
  • Duplicate values? If multiple nodes on a path have the same maximum value, the comparison node.val >= max_so_far correctly handles this.

Examples

1

Example 1

Input:

root = [3,1,4,3,null,1,5]

Output:

4

Note:

The dominant nodes are:

  • 3 (root): max_path_val = -Infinity (conceptually), 3 >= -Infinity. Dominant.
  • 3 (left child of 1): max_path_val from root to parent 1 is 3. 3 >= 3. Dominant.
  • 4 (right child of 3): max_path_val from root to parent 3 is 3. 4 >= 3. Dominant.
  • 5 (right child of 4): max_path_val from root to parent 4 is 4. 5 >= 4. Dominant. Nodes 1 (left child of 3) and 1 (left child of 4) are not dominant as their values are less than their respective path maximums.
2

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.

3

Example 3

Input:

root = [1,2,3]

Output:

3

Note:

The dominant nodes are:

  • 1 (root): Dominant.
  • 2 (left child of 1): max_path_val from root to parent 1 is 1. 2 >= 1. Dominant.
  • 3 (right child of 1): max_path_val from root to parent 1 is 1. 3 >= 1. Dominant.
4

Example 4

Input:

root = []

Output:

0

Note:

An empty tree has no nodes, thus no dominant nodes.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is between 0 and 10^5.
  • Node values (val) are between -10^4 and 10^4.
  • The tree is a valid binary tree (no cycles).

Out of scope

  • Handling non-numeric node values.
  • Modifying the tree structure.
  • Validating the input tree for cycles or malformed nodes.

What interviewers evaluate

  • Correctness: Does the solution accurately identify and count all dominant nodes?
  • Efficiency: Is the solution optimal in terms of time and space complexity for tree traversal?
  • Clarity: Is the code well-structured, readable, and easy to understand?
  • Edge Cases: Does the solution gracefully handle an empty tree or a tree with a single node?

Loading editor...