Problem statement

https://binarysearch.com/problems/Enlarge-BST/

Solution

Equal to Leetcode 1038. Binary Search Tree to Greater Sum Tree.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def __init__(self):
        self.total = 0
    
    def solve(self, root):
        if not root: return
        self.solve(root.right)
        self.total += root.val
        root.val = self.total
        self.solve(root.left)
        return root