1038. Binary Search Tree to Greater Sum Tree

Medium

Problem:

Given a binary search tree, calculate the sum of nodes with values between low and high, inclusive.

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

Solution:

To find a value that is equal to or greater than oneself, you can simply compute the sum of the right child node, including oneself. This is because, in the BST structure, the right child node always has a value greater than the parent node.

Since we move in the order of 'right-parent-left', we can recognize that it corresponds to an in-order traversal starting from the right child.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    added: int = 0
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        self.bstToGst(root.right)
        
        self.added += root.val
        root.val = self.added
        
        self.bstToGst(root.left)
        
        return root