https://leetcode.com/problems/convert-bst-to-greater-tree

In this problem for each node we need to calculate sum of all values, which are bigger than this node, so we need to visit nodes, starting with the biggest and going to the smallest. The way how you can do it is inorder traversal, but with one small modification: instead of left -> root -> right, we will go right -> root -> left. Also we will keep global variable self.total, where we accumulate our values.

  1. if not root means, that we go outside our tree, we need to return.
  2. Next, we visit right subtee, using recursion, so far problem sovled for right part.
  3. In self.total we now have sum of all nodes in the right subtree, we add root.val and write this value to root.val.
  4. Now, we can traverse left subtee.

Complexity: time complexity is O(n) to travese all tree, space complexity is O(h): height of our tree.

class Solution(object):
    def __init__(self):
        self.total = 0

    def convertBST(self, root):
        if not root: return
        self.convertBST(root.right)
        self.total += root.val
        root.val = self.total
        self.convertBST(root.left)
        return root

If you like the solution, you can upvote it on leetcode discussion section: Problem 0538