We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Convert BST to Greater Tree

Number: 538

Difficulty: Medium

Paid? No

Companies: Amazon, Meta

Problem Description

Given the root of a Binary Search Tree (BST), transform it into a Greater Tree such that every node's new value is equal to the sum of its original value plus the sum of all keys greater than the original node’s key in the BST.

Key Insights

  • Use the BST property: nodes in the right subtree always have greater keys.
  • Traverse the tree in reverse in-order (right, node, left) to process nodes in descending order.
  • Maintain a running sum to accumulate values already visited.
  • Update each node during the traversal by adding the running sum to its original value.

Space and Time Complexity

Time Complexity: O(n) (Each node is visited once.) Space Complexity: O(h) (h is the height of the tree, representing the recursion or stack height.)

Solution

The solution uses a reverse in-order traversal (visiting right subtree, node, then left subtree) because it processes nodes from the largest to the smallest. As you traverse the tree, you maintain a running sum of the values that have been visited so far. For each node, update its value by adding the running sum to its original value. This modified value properly represents the original value plus the sum of all greater keys in the BST.

Code Solutions

# 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:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Initialize running sum
        self.running_sum = 0
        
        def reverse_inorder(node: Optional[TreeNode]):
            # Base case: if node is None, simply return
            if not node:
                return
            # Traverse right subtree first (larger values)
            reverse_inorder(node.right)
            # Update running sum and node's value
            self.running_sum += node.val
            node.val = self.running_sum
            # Traverse left subtree
            reverse_inorder(node.left)
        
        reverse_inorder(root)
        return root
← Back to All Questions