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 tex_3ca65799320efe93e56ebdc3f48e6013 Teaching Kids Programming - Split Tree to Maximize Product (Recursive Depth First Search Algorithm) algorithms DFS recursive teaching kids programming youtube video can be computed via either Depth First Search or Breadth First Search Algorithm. Then for each subtree sum tex_e63be394c81829edba551a57db63d230 Teaching Kids Programming - Split Tree to Maximize Product (Recursive Depth First Search Algorithm) algorithms DFS recursive teaching kids programming youtube video , we can compute the product which is tex_2acf3fd202570deedab0784e3bcadc7e Teaching Kids Programming - Split Tree to Maximize Product (Recursive Depth First Search Algorithm) algorithms DFS recursive teaching kids programming youtube video . We want to maximize the tex_83651ef483f616a73e483203b4efa7fb Teaching Kids Programming - Split Tree to Maximize Product (Recursive Depth First Search Algorithm) algorithms DFS recursive teaching kids programming youtube video .

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

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

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

GD Star Rating
loading...
736 words
Last Post: Teaching Kids Programming - Find Partition Equal Subset Sum (Bottom Up Dynamic Programming Algorithm)
Next Post: Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm

The Permanent URL is: Teaching Kids Programming – Split Tree to Maximize Product (Recursive Depth First Search Algorithm)

Leave a Reply