# Solving Leetcode Interviews in Seconds with AI: Convert BST to Greater Tree


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "538" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST. 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: 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]  Example 2:  Input: root = [0,null,1] Output: [1,null,1]    Constraints:  The number of nodes in the tree is in the range [0, 104]. -104 <= Node.val <= 104 All the values in the tree are unique. root is guaranteed to be a valid binary search tree.    Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/ 

	# Explanation
	*   **Reverse Inorder Traversal:** Traverse the BST in a reverse inorder manner (right, node, left). This allows us to visit nodes in descending order of their values.
*   **Maintain Cumulative Sum:** Keep track of a cumulative sum as we traverse. For each node, add the current cumulative sum to its value and update the cumulative sum.
*   **Modify Node Values:** The modified node values will represent the original value plus the sum of all greater values.

*   **Time Complexity:** O(N), where N is the number of nodes in the BST.
*   **Space Complexity:** O(H), where H is the height of the BST (call stack due to recursion). In the worst-case scenario (skewed tree), H = N. In the best and average case (balanced tree), H = log N.

	
	# Code
	```python
	class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        self.cumulative_sum = 0

        def reverse_inorder(node: TreeNode):
            if not node:
                return

            reverse_inorder(node.right)
            self.cumulative_sum += node.val
            node.val = self.cumulative_sum
            reverse_inorder(node.left)

        reverse_inorder(root)
        return root
	```