Counting Maximal Value Roots in Binary Tree using Depth First Search Algorithm

Given a binary tree root, count and return the number of nodes where its value is greater than or equal to the values of all of its descendants.

For example, given

   6
  / \
 3   2
    / \
   6   4

Return 4 since all nodes except for 2 meet the criteria.

Example 1
Input
root = [6, [3, null, null], [2, [6, null, null], [4, null, null]]]
Output
4

Depth First Search Algorithm to Count the Maximal Value Roots in Binary Tree

Let’s define a DFS function that returns the maximum of the values in the current subtree. Then, we can increment the answer if the current node’s value is larger than its left and right max values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int countMaxValueRoots(Tree* root) {
    int ret = 0;
    function<int(Tree*)> dfs = [&](Tree* root) {
        if (!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if (root->val >= max(left, right)) {
            ret ++;
        }
        return max({root->val, left, right});
    };
   dfs(root);    
   return ret;
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
int countMaxValueRoots(Tree* root) {
    int ret = 0;
    function<int(Tree*)> dfs = [&](Tree* root) {
        if (!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if (root->val >= max(left, right)) {
            ret ++;
        }
        return max({root->val, left, right});
    };
   dfs(root);    
   return ret;
}

The above DFS Algorithm runs at O(N) time where N is the number of the nodes in the binary tree. The space complexity is O(N) as we are using Recursion to do the DFS.

–EOF (The Ultimate Computing & Technology Blog) —