Minimum Binary Tree Partition

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.val + sum_tree(root.left) + sum_tree(root.right)

def find_target_subtree(root, target_sum):
    if not root:
        return None, None

    # Check if current node is the target
    if root.val == target_sum:
        return root, None

    # Search for target in left subtree
    left_subtree, right_subtree = find_target_subtree(root.left, target_sum)
    if left_subtree:
        return left_subtree, root.right

    # Search for target in right subtree
    left_subtree, right_subtree = find_target_subtree(root.right, target_sum - root.val)
    if right_subtree:
        return root.left, right_subtree

    return None, None

# Example usage
root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(6, TreeNode(7), TreeNode(8)))
left_subtree, right_subtree = partition_tree(root)

if left_subtree:
    print("Left subtree:", left_subtree.val)
else:
    print("No valid partition found")

if right_subtree:
    print("Right subtree:", right_subtree.val)
else:
    print("No valid partition found")