BST to greater sum tree

Time: O(n)

Space: O(h)

Intuition

In-order traversal visits BST in ascending order. Reverse in-order (rightâ†’nodeâ†’left) visits in descending order. Maintain a running sum; update each node's value.

Algorithm

1Do reverse in-order traversal (right subtree first).
2Maintain running sum. At each node: sum += node.val; node.val = sum.

Example Walkthrough

Input: BST=[4,1,6,0,2,5,7]

1.Visit 7â†’sum=7. Visit 6â†’sum=13. Visit 5â†’sum=18. Visit 4â†’sum=22. Visit 2â†’sum=24. Visit 1â†’sum=25. Visit 0â†’sum=25.

Output: Tree with updated values

Common Pitfalls

•This is a simple Morris traversal or recursive reverse in-order â€” no extra space needed with Morris.

BST to greater sum tree.java

Java

// Approach: Reverse in-order traversal (right-root-left). Maintain a running suffix sum.
// Update each node's value with the accumulated suffix sum.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    static int totalSum;

    public static void transformTree(Node root) {
        totalSum = 0;
        solve(root);
    }

    static void solve(Node root) {
        if (root == null)
            return;

        solve(root.right);

        int rootVal = root.data;
        root.data = totalSum;
        totalSum += rootVal;

        solve(root.left);
    }
}

Was this solution helpful?