Minimum Binary Tree Partition

December 29, 2023

Problem # Given a binary tree, partition it into two subtrees such that the sum of values in the left subtree is equal to the sum of values in the right subtree. If multiple answers exist, return any one. If no answer exists, return NULL. Solution # class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def partition_tree(root): if not root: return None, None # Calculate sum of all nodes in the tree total_sum = sum_tree(root) # Find the target sum for the left subtree target_sum = total_sum // 2 # Search for the target sum in the tree left_subtree, right_subtree = find_target_subtree(root, target_sum) # Check if a valid partition exists if left_subtree and sum_tree(left_subtree) == target_sum: return left_subtree, right_subtree return None, None def sum_tree(root): if not root: return 0 return root. ...