LeetCode 663: Equal Tree Partition Solution in Python – A Step-by-Step Guide

What Is LeetCode 663: Equal Tree Partition?

In LeetCode 663: Equal Tree Partition, you’re given the root of a binary tree (nodes with val, left, and right attributes), and your task is to determine if there exists an edge you can remove to split the tree into two subtrees with equal sums of their node values. Return True if such a split is possible, False otherwise. For example, with root = [5, 10, 10, null, null, 2, 3], the total sum is 50, and cutting below 5 gives subtrees [5] (sum 5) and [10, 10, 2, 3] (sum 45), but cutting below 10 gives [10, 2, 3] (sum 25) and [5, 10] (sum 25), returning True. This problem tests your ability to compute subtree sums and find a balanced partition.

Problem Statement

• Input:
• root: Root node of a binary tree.
• Output: A boolean—True if equal partition exists, False otherwise.
• Rules:
• Remove one edge to split into two subtrees.
• Subtrees must have equal sums.
• Sum = total value of all nodes in subtree.

Constraints

• Number of nodes: 1 to 10⁴.
• -10⁵ ≤ Node.val ≤ 10⁵.

Examples

• Input: root = [5, 10, 10, null, null, 2, 3]
• Output: True (Split at 10: [10, 2, 3] and [5, 10], both sum to 25)
• Input: root = [1, 2, 10, null, null, 20, 2]
• Output: False (No equal split possible)
• Input: root = [0, 1, -1]
• Output: True (Split at 0: [1] and [-1], both sum to 0)

These examples set the tree—let’s solve it!

Understanding the Problem: Finding the Split

To solve LeetCode 663: Equal Tree Partition in Python, we need to check if we can remove one edge in a binary tree to create two subtrees with equal sums. A brute-force approach—cutting each edge and computing sums—would be O(n²), inefficient for n ≤ 10⁴. Since subtree sums relate to the total tree sum, we can optimize by collecting sums once and checking for half the total. We’ll use:

• Best Solution (DFS with Sum Tracking): O(n) time, O(n) space—fast and clear.
• Alternative Solution (BFS with Subtree Sums): O(n) time, O(n) space—level-based but complex.

Let’s start with the DFS solution, breaking it down for beginners.

Best Solution: DFS with Sum Tracking

Why This Is the Best Solution

The DFS with sum tracking approach is the top choice for LeetCode 663 because it’s efficient—O(n) time with O(n) space—and uses depth-first search to compute all subtree sums in one pass, storing them to quickly check for an equal split. It fits constraints (n ≤ 10⁴) perfectly and is intuitive once you see the sum collection. It’s like exploring the tree and marking sums to find a perfect cut!

How It Works

Think of this as a sum collector:

• Step 1: DFS for Subtree Sums:
• Recursively compute sum of each subtree, store in a list.
• Step 2: Compute Total Sum:
• Total sum of tree = sum of root subtree.
• Step 3: Check for Split:
• Target = total_sum // 2.
• If total_sum is even and target exists in sums (excluding total_sum), return True.
• Step 4: Return Result:
• Return False if no split found.

It’s like a balance finder—sum and match!

Step-by-Step Example

Example: root = [5, 10, 10, null, null, 2, 3]

• Step 1: DFS:
• Right [10, 2, 3]:
• [2]: Sum = 2, sums = [2].
• [3]: Sum = 3, sums = [2, 3].
• [10, 2, 3]: Sum = 15, sums = [2, 3, 15].
• Left [10]: Sum = 10, sums = [2, 3, 15, 10].
• Root [5, 10, 10]: Sum = 50, sums = [2, 3, 15, 10, 25, 50].
• Step 2: Total_sum = 50.
• Step 3: Target = 50 // 2 = 25.
• 25 in sums (from [10, 2, 3]), total_sum % 2 = 0, return True.
• Output: True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def checkEqualTree(self, root: TreeNode) -> bool:
        # Step 1: Initialize list for subtree sums
        sums = []

        # Step 2: DFS to collect subtree sums
        def dfs(node):
            if not node:
                return 0

            # Compute sum of left and right subtrees
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)

            # Total sum of this subtree
            total = node.val + left_sum + right_sum

            # Add to sums (except root sum, added later)
            sums.append(total)

            return total

        # Get total tree sum
        total_sum = dfs(root)

        # Step 3: Check for equal split
        if total_sum % 2 != 0:
            return False  # Odd sum can't be split equally

        target = total_sum // 2
        # Check if target exists in sums (excluding total_sum itself)
        return target in sums[:-1]  # Exclude last sum (total_sum)

• Lines 1-6: TreeNode class (standard).
• Line 10: Init: List for subtree sums.
• Lines 13-26: DFS:
• Recursively compute sums, store each subtree sum, return total.
• Line 29: Get total_sum from root.
• Lines 32-36: Check:
• Even total_sum required, target = half, check sums excluding total.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(n)—sums list.

This is like a tree balancer—sum and split!

Alternative Solution: BFS with Subtree Sums

Why an Alternative Approach?

The BFS with subtree sums approach uses breadth-first search—O(n) time, O(n) space. It’s more level-based, computing sums bottom-up, but requires managing parent pointers or extra traversal, making it less intuitive. It’s like leveling the tree and checking sums as you climb!

How It Works

Picture this as a level climber:

• Step 1: BFS to collect nodes and sums:
• Queue nodes, track sums bottom-up.
• Step 2: Build sum map:
• Map each node to its subtree sum.
• Step 3: Check for split:
• Total sum = root sum, target = half, check map.
• Step 4: Return result.

It’s like a sum ladder—climb and check!

Step-by-Step Example

Example: Same as above

• Step 1: BFS:
• Queue: [5], [10, 10], [2, 3].
• Step 2: Sums:
• 2: 2, 3: 3, 10(right): 15, 10(left): 10, 5: 50.
• Step 3: Total_sum = 50, target = 25, 25 in sums, return True.
• Output: True.

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def checkEqualTree(self, root: TreeNode) -> bool:
        # Step 1: BFS to collect nodes and parents
        queue = deque([root])
        parent = {root: None}
        sums = {}

        # Step 2: Compute subtree sums bottom-up
        while queue:
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
                parent[node.left] = node
            if node.right:
                queue.append(node.right)
                parent[node.right] = node

        # Post-order sum calculation
        def get_sum(node):
            if not node:
                return 0
            total = node.val + get_sum(node.left) + get_sum(node.right)
            sums[node] = total
            return total

        total_sum = get_sum(root)

        # Step 3: Check for equal split
        if total_sum % 2 != 0:
            return False

        target = total_sum // 2
        for node, s in sums.items():
            if s == target and node != root:
                return True

        # Step 4: Return result
        return False

• Lines 4-19: BFS:
• Queue nodes, track parents, collect sums.
• Lines 22-28: Compute sums recursively.
• Lines 31-38: Check:
• Even sum, target in sums excluding root.
• Time Complexity: O(n)—two passes.
• Space Complexity: O(n)—queue and sums.

It’s a level balancer—climb and match!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n) time, O(n) space, single pass, clear.
• Cons: Recursion stack.
• BFS (Alternative):
• Pros: O(n) time, O(n) space, level-wise.
• Cons: More bookkeeping.

DFS wins for simplicity.

Additional Examples and Edge Cases

• Input: [1]
• Output: False.
• Input: [0, 1, -1]
• Output: True.

Both handle these well.

Complexity Breakdown

• DFS: Time O(n), Space O(n).
• BFS: Time O(n), Space O(n).

DFS is optimal for ease.

Key Takeaways

• DFS: Sum tracking—smart!
• BFS: Level summing—clear!
• Partition: Trees are fun.
• Python Tip: Recursion rocks—see Python Basics.

Final Thoughts: Split That Tree

LeetCode 663: Equal Tree Partition in Python is a fun tree challenge. DFS with sum tracking offers clarity and efficiency, while BFS provides a level-based alternative. Want more? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 437: Path Sum III. Ready to cut? Head to Solve LeetCode 663 on LeetCode and partition that tree today!