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
Input1 / \ 2 3 / \ 4 5Output
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.
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) —
loading...
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