Convert Binary tree into Sum tree

Problem Statement

Given a binary tree, convert it to a Sum Tree where each node contains the sum of the left and right subtrees in the original tree. The values of leaf nodes are changed to 0.

Example:

• Node 10 becomes: (-2 + 8 + -4) + (6 + 7 + 5) = 2 + 18 = 20
• Node -2 becomes: 8 + -4 = 4
• Node 6 becomes: 7 + 5 = 12
• Leaf nodes become 0

Approach 1: Brute Force (Two Pass - Calculate Sum Separately)

Intuition

For each node, calculate the sum of its left subtree and right subtree separately, then update the node's value. This requires traversing the subtree for each node.

Algorithm

1. For each node, traverse its left subtree to get the sum
2. Traverse its right subtree to get the sum
3. Store original value, update node value to left_sum + right_sum
4. Recursively convert left and right subtrees

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int getSum(TreeNode root) {
        if (root == null) return 0;
        return root.val + getSum(root.left) + getSum(root.right);
    }
    
    public void convertToSumTreeBruteForce(TreeNode root) {
        if (root == null) return;
        
        // Get sum of left and right subtrees
        int leftSum = getSum(root.left);
        int rightSum = getSum(root.right);
        
        // Store original value for children's conversion
        int oldVal = root.val;
        
        // Update current node
        root.val = leftSum + rightSum;
        
        // Convert children
        convertToSumTreeBruteForce(root.left);
        convertToSumTreeBruteForce(root.right);
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - For each node, we calculate sum of subtree which takes O(n)
• Space Complexity: O(n) - Recursion stack for skewed tree

Approach 2: Optimal (Single Pass - Bottom-Up Conversion)

Intuition

Convert the tree bottom-up. When converting a node, its children are already converted. Use the original values stored during recursion to calculate the sum and return it for parent's use.

Algorithm

1. Recursively convert left and right subtrees first
2. Each recursive call returns the sum of original subtree
3. Update current node's value using returned sums
4. Return original value + left sum + right sum for parent

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // Returns sum of original subtree rooted at node
    public int convertToSumTree(TreeNode root) {
        if (root == null) return 0;
        
        // Leaf node
        if (root.left == null && root.right == null) {
            int oldVal = root.val;
            root.val = 0;
            return oldVal;
        }
        
        // Get sum of left and right subtrees (original values)
        int leftSum = convertToSumTree(root.left);
        int rightSum = convertToSumTree(root.right);
        
        // Store original value
        int oldVal = root.val;
        
        // Update node value
        root.val = leftSum + rightSum;
        
        // Return sum of original subtree
        return oldVal + leftSum + rightSum;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Each node is visited exactly once
• Space Complexity: O(h) - Recursion stack depth, where h is height of tree

Key Takeaways

1. Bottom-up approach is key to achieving O(n) time complexity
2. Return original subtree sum during recursion to avoid recalculating
3. Leaf nodes become 0 in a sum tree
4. The pattern of "transform and return value" is common in tree modification problems
5. Always consider what information needs to be passed up during recursion