Skip to content

3997. Count Dominant Nodes in a Binary Tree

Description

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.

Solutions

Solution 1: DFS

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 \(\textit{mx} = \max(\textit{leftMax}, \textit{rightMax}, \textit{node.val})\). If \(\textit{mx} = \textit{node.val}\), the node is dominant and the answer is incremented by one. Finally return \(\textit{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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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;
}

Comments