1038. Binary Search Tree to Greater Sum Tree

MediumView on LeetCode

Tree Depth-First Search Binary Search Tree Binary Tree

Time: O(n)

Space: O(n)

Intuition

Reverse in-order (right, node, left) accumulates sum from largest to smallest BST value.

Algorithm

1DFS right first, then visit and add running sum, then left.
2node.val += runningSum; runningSum = node.val.

Common Pitfalls

•Traverse right before left to process larger values first.

1038.cs

// Approach: Reverse in-order traversal (right → node → left); accumulate a running prefix sum and assign it to each node.
// Time: O(n) Space: O(n)

public class Solution
{
    int prefix = 0;
    public TreeNode BstToGst(TreeNode root)
    {
        if (root.right != null)
            BstToGst(root.right);

        prefix += root.val;
        root.val = prefix;

        if (root.left != null)
            BstToGst(root.left);

        return root;
    }
}

Was this solution helpful?