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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Convert BST to Greater Tree

Difficulty: Medium

Problem Description

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.

Key Insights

  • A Binary Search Tree (BST) is structured such that for any node, all values in the left subtree are less, and all values in the right subtree are greater.
  • To convert the BST to a Greater Tree, we need to traverse the tree in a manner that allows us to accumulate the sum of the keys greater than the current node.
  • A reverse in-order traversal (right-root-left) allows us to visit nodes in descending order, making it easy to keep track of the cumulative sum of values.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the BST, as we visit each node exactly once. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack. In the worst case (unbalanced tree), this could be O(N), but in a balanced tree, it would be O(log N).

Solution

The problem can be solved using a reverse in-order traversal technique which allows us to visit each node starting from the largest value down to the smallest. During the traversal, we maintain a running sum that accumulates the values of nodes we have already visited. For each node, we update its value to be the sum of its original value and the running sum. We then update the running sum to include the current node's new value before moving to the left subtree.

Code Solutions

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

def convertBST(root: TreeNode) -> TreeNode:
    # Initialize the cumulative sum
    total_sum = 0

    # Helper function for reverse in-order traversal
    def reverse_inorder(node):
        nonlocal total_sum
        if not node:
            return
        
        # Traverse the right subtree first (greater values)
        reverse_inorder(node.right)
        
        # Update the total_sum and the current node's value
        total_sum += node.val
        node.val = total_sum
        
        # Traverse the left subtree
        reverse_inorder(node.left)

    reverse_inorder(root)
    return root
← Back to All Questions