Teaching Kids Programming – Subtree with Maximum Value via Recursive Depth First Search Algorithm

ACMer

4 years ago

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the maximum sum of a subtree. A subtree is defined to be some node in root including all of its descendants. A subtree sum is the sum of all the node values in the subtree. A subtree can be null in which case its sum is 0.

Constraints
1 ≤ n ≤ 100,000 where n is the number of nodes in root
    3
   / \
  0   2
     /
    0

Compute the Maximum Subtree Sum in a Binary Tree with DFS Algorithm

We can use the Recursive DFS (Depth First Search) Algorithm to compute the sum of any given subtree, and then we just need to update the maximum sum that we have seen so far.

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

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

Time complexity is O(N) and the space complexity is O(N) where N is the number of the nodes in the binary tree.

–EOF (The Ultimate Computing & Technology Blog) —

344 words
Last Post: Teaching Kids Programming - Reverse a Graph (Adjacency List)
Next Post: How to Truncate a String in PHP?

The Permanent URL is: Teaching Kids Programming – Subtree with Maximum Value via Recursive Depth First Search Algorithm (AMP Version)

Compute the Maximum Subtree Sum in a Binary Tree with DFS Algorithm

Related posts: