Teaching Kids Programming – Counting Maximal Value Roots in Binary Tree (Recursive Post-Order Traversal – DFS Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Constraints
n ≤ 100,000 where n is the number of nodes in root
Example 1
Input

Output
4
Explanation
Since all nodes except for 2 meet the criteria.

Hint:
what if at every moment we have maximum from left and right sub-tree and then transfer maximum of {root,left,right} upwards? recursion?

Recursive Post-order Traversal (Depth First Search Algorithm) – Count Nodes with Maximum Subtree Value

We can bruteforce each node, which takes O(N) time, but it takes O(N) to check if current node is the maximum of the subtree, overall this is O(N^2) qudratic time complexity – inefficient.

We can do post-order traversal, and for each node, we need to return the maximum value for the current subtree, in order to comptue the max value, we can compare three values: the current node’s value, the left maximum and the right maximum which can be recursively obtained.

And, when recursion bottoms up, we can check if current node is the maximum, if yes, increment the counter.

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

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        ans = 0
 
        def dfs(root):
            if not root:
                return -math.inf
            nonlocal ans
            left = dfs(root.left)
            right = dfs(root.right)
            if root.val >= left and root.val >= right:
                ans += 1
            return max(left, right, root.val)
 
        dfs(root)
        return ans

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        ans = 0

        def dfs(root):
            if not root:
                return -math.inf
            nonlocal ans
            left = dfs(root.left)
            right = dfs(root.right)
            if root.val >= left and root.val >= right:
                ans += 1
            return max(left, right, root.val)

        dfs(root)
        return ans

Time complexity is O(N) – linear, as each node in the tree is visited once. And the space complexity is O(N) due to the calling stack imposed by the Recursion.

See also: Counting the Maximal Value Roots in Binary Tree using Depth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —