Leetcode 1038. Binary Search Tree to Greater Sum Tree

Problem statement

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Solution

The idea is to traverse our tree, starting from the bigger elements, that is first we go to the right, then update self.total is sum of all values which are > root.val, make root.val equal to self.total and then traverse the right subtree.

Complexity

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

Code

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