---
link: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
tags: tree, bt
---

# 1038. Binary Search Tree to Greater Sum Tree
Given the root of a binary **search** tree with distinct values, modify it so that every `node` has a new value equal to the sum of the values of the original tree that are greater than or equal to `node.val`.

As a reminder, a *binary search tree* is a tree that satisfies these constraints:

- The left subtree of a node contains only nodes with keys **less than** the node's key.
- The right subtree of a node contains only nodes with keys **greater than** the node's key.
- Both the left and right subtrees must also be binary search trees.

**Example 1:**

****

Input: [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]

## Question

## Solution: Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def bstToGst(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.helper(root, 0)
        return root
    
    def helper(self, node, total):
        if node is None:
            return 0
    
        r_total = self.helper(node.right, total)
        
        nr_total = node.val + max(r_total, total)
        node.val = nr_total        
        
        l_total = self.helper(node.left, nr_total)
                
        return max(nr_total, l_total)

 helper(4, 0)                       --> r_total = 26, nr_total = 4 + max(26, 0) = 30, return max(36, 30) = 36
    helper(1, 30)                   --> r_total = 35, nr_total = 1 + max(35, 30) = 36, return max(36, 36) = 36
        helper(0, 36)               --> r_total = 0, nr_total = 0 + max(0, 36) = 36, return max(0, 36) = 36
            helper(null, 36)        --> return 0
            helper(null, 36)        --> return 0
        helper(2, 30)               --> r_total = 33, nr_total = 2 + max(30, 33) = 35, return max(0, 35) = 35
            helper(null, 35)        --> return 0
            helper(3, 30)           --> r_total = 0, nr_total = 3 + max(30, 0) = 33, return max(0, 33) = 33
                helper(null, 33)    --> return 0
                helper(null, 30)    --> return 0
    helper(6, 0)                    --> r_total = 15, nr_total = 6 + max(15, 0) = 21; return max(21, 26) = 26
        helper(5, 21)               --> r_total = 0, nr_total = 5 + max(0, 21) = 26, return max(26, 0) = 26
            helper(null, 21)        --> return 0
            helper(null, 26)        --> return 0
        helper(7, 0)                --> r_total = 8, nr_total = 7 + max(8, 0) = 15, return max(15, 0) = 15
            helper(null, 15)        --> return 0
            helper(8, 0)            --> r_total = 0; nr_total = 8 + 0 = 8, return max(8, 0) = 8
                helper(null, 8)     --> return 0
                helper(null, 0)     --> return 0


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def bstToGst(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.helper(root, 0)
        return root
    
    def helper(self, node, total):
        if node is None:
            return 0
    
        r_total = self.helper(node.right, total) 
        
        nr_total = node.val + max(r_total, total)
        node.val = nr_total
        
        l_total = self.helper(node.left, nr_total)
                
        return max(nr_total, l_total)

## Solution: Java