Transform to Sum Tree

Time: O(n)

Space: O(h)

Intuition

Each node in a sum tree should store the sum of values in its left and right subtrees from the original tree. This naturally suggests a postorder traversal: compute children first, then update the current node. Returning subtree totals from recursion lets each parent compute its new value in one pass.

Algorithm

1Define a recursive function solve(node) that returns the total sum of the original subtree rooted at node after transformation.
2Base case: if node is null, return 0.
3Store old = node.data (original value).
4Recursively compute leftSum = solve(node.left) and rightSum = solve(node.right).
5Set node.data = leftSum + rightSum (sum-tree requirement).
6Return node.data + old so parent receives total original subtree sum.
7Call solve(root) from toSumTree(root).

Example Walkthrough

Input: Tree: 10 with left=2 and right=3

1.Leaf 2: leftSum=0, rightSum=0, node becomes 0, return 0+2=2.
2.Leaf 3: leftSum=0, rightSum=0, node becomes 0, return 0+3=3.
3.Root 10: leftSum=2, rightSum=3, node becomes 5, return 5+10=15.
4.Final transformed tree values: root=5, left=0, right=0.

Output: Root now stores 5; each leaf stores 0

Common Pitfalls

•Use postorder, not preorder; updating parent first would lose needed original child sums.
•Store old node value before overwrite, otherwise parent total becomes incorrect.
•Space is recursion stack O(h), not O(1), where h is tree height.

Transform to Sum Tree.java

Java

// Structure for Tree Node

class Node {

    int data;
    Node left, right;

    // Constructor
    Node(int val) {
        data = val;
        left = null;
        right = null;
    }
};

// Approach: Postorder DFS. For each node, first compute sums of left and right subtrees.
// Replace node.data with leftSum + rightSum, and return (oldValue + new node.data) upward.
// This transforms the tree in-place into a sum tree.
// Time: O(n) Space: O(h)

class Solution {

    public void toSumTree(Node root) {
        solve(root);
    }

    private int solve(Node node) {
        if (node == null) {
            return 0;
        }
        // Recursively compute left and right subtree sums
        int old = node.data;
        node.data = solve(node.left) + solve(node.right);
        // Return the total sum including the original node value
        return node.data + old;
    }
}

Was this solution helpful?