Teaching Kids Programming – Split Tree to Maximize Product (Recursive Depth First Search Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, consider deleting an edge in the tree so that the tree becomes disjoint with two trees. Then, take the sum of each subtree and multiply the two numbers. Return the largest such product we can get after deleting one edge.

Given the root of a binary tree, split the binary tree into two subtrees by removing one edge such that the product of the sums of the subtrees is maximized. Return the maximum product of the sums of the two subtrees.

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

    1
   / \
  2   3
     / \
    4   5

Output
50
Explanation
If we delete the 3 – 5 edge, then we can have (1 + 2 + 3 + 4) * 5 = 50
If we know the sum of a subtree, the answer is max( (total_sum – subtree_sum) * subtree_sum) in each node.

Maximum Product of Splitted Binary Tree via Recursion Depth First Search Algorithm

The sum of the binary tree can be computed via either Depth First Search or Breadth First Search Algorithm. Then for each subtree sum , we can compute the product which is . We want to maximize the .

By removing an edge, we have two sub trees. We can bruteforce all these possibilities.

# 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 maxProductBySplittingBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root:
                return 0
            return root.val + dfs(root.left) + dfs(root.right)        
        ans = 0
        def dfs2(root):
            if not root:
                return 0
            nonlocal ans
            cur = root.val + dfs2(root.left) + dfs2(root.right)
            ans = max(ans, (total - cur) * cur)
            return cur
        total = dfs(root)
        dfs2(root)
        return ans

The DFS is performed twice. The first time we get the total sum, and then the second time we maximize the product. We can alternatively store all possible subtree sums in a hash set and iterate over them to compute the max product.

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxProductBySplittingBinaryTree(self, root):
        s = set()
        ans = -math.inf
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            s.add(left)
            right = dfs(root.right)            
            s.add(right)
            total = left + right + root.val
            s.add(total)            
            return total
        total = dfs(root)
        print(total, s)
        for i in s:
            ans = max(ans, (total - i) * i)
        return ans

The time and space complexity is O(N) where N is the number of Nodes in the binary tree.

–EOF (The Ultimate Computing & Technology Blog) —