algoadvance

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 sum of the keys greater than or equal to the original key in BST.

Clarifying Questions:

1. Can the BST contain negative numbers?
   • Yes, the BST can contain any integer values.
2. Is there a restriction on the size of the tree?
   • No specific information is provided, so we will assume that the tree can be of any size that fits within typical system constraints.

Strategy:

To solve this problem, we can perform a Reverse Inorder Traversal of the BST:

• Inorder Traversal of BST gives us elements in ascending order.
• Reverse Inorder Traversal (i.e., visit right, root, left) will give us elements in descending order.

By traversing the tree in reverse inorder fashion, we can keep a cumulative sum of all the nodes we have visited so far and update the current node’s value to this cumulative sum.

Code:

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:
        """
        Convert the BST to a Greater Tree.
        :param root: TreeNode - the root of the BST
        :return: TreeNode - the root of the modified Greater Tree
        """
        self.cumulative_sum = 0
        
        def reverse_inorder(node):
            if not node:
                return
            # Traverse the right subtree first
            reverse_inorder(node.right)
            # Visit the node
            self.cumulative_sum += node.val
            node.val = self.cumulative_sum
            # Traverse the left subtree
            reverse_inorder(node.left)
        
        reverse_inorder(root)
        return root

Time Complexity:

• The time complexity of this solution is (O(n)), where (n) is the number of nodes in the tree. This is because each node is visited exactly once in the reverse inorder traversal.
• The space complexity is (O(h)), where (h) is the height of the tree. This space is used by the recursion stack. In the worst case, (h) could be (n) (for a skewed tree), making the space complexity (O(n)). In the average case, for a balanced tree, the space complexity would be (O(\log n)).

This completes the solution for converting a given BST to a Greater Tree.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?