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

Binary Search Tree to Greater Sum 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

  • The problem requires transforming a Binary Search Tree into a Greater Tree.
  • The transformation involves summing keys greater than each node's key.
  • In a BST, the in-order traversal can be used to visit nodes in ascending order.
  • A reverse in-order traversal (right-root-left) is suitable to accumulate the sums since it processes nodes in descending order.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, since each node is visited once. Space Complexity: O(h) - where h is the height of the tree, due to the recursion stack.

Solution

The algorithm uses a reverse in-order traversal to accumulate the sum of all node values greater than the current node. A running total is maintained during traversal, which is updated as we visit each node. This way, we can modify each node's value in-place.

  1. Start the traversal from the rightmost node (which is the largest).
  2. Maintain a variable to keep track of the cumulative sum of visited nodes.
  3. For each node, update its value by adding the cumulative sum.
  4. Update the cumulative sum to include the current node's new value before moving to the left child.

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):
    total = 0
    
    def reverse_inorder(node):
        nonlocal total
        if not node:
            return
        reverse_inorder(node.right)  # Visit right subtree
        total += node.val             # Update the total
        node.val = total              # Update the node's value
        reverse_inorder(node.left)    # Visit left subtree

    reverse_inorder(root)
    return root
← Back to All Questions