algoadvance

Leetcode 538. Convert BST to Greater Tree

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.

Clarifying Questions

  1. Is the input BST always valid?
    • Yes, you can assume the BST is always valid.
  2. Can the BST contain negative values?
    • Yes, it can contain negative values.
  3. What should be returned?
    • The root of the modified BST should be returned.
  4. Can the BST have duplicate values?
    • No, a valid BST does not contain duplicate values.

Strategy

To convert the BST to a Greater Tree, we need to ensure that every node’s value is updated to the sum of its value plus all nodes with values greater than its own.

Steps to achieve this:

  1. Perform a reverse in-order traversal (Right -> Node -> Left). This allows us to process nodes in descending order.
  2. Maintain a cumulative sum while traversing the tree.
  3. For each node, update its value with the cumulative sum and then update the cumulative sum to include the node’s original value.

Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    
    TreeNode(int val) { 
        this.val = val; 
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int cumulativeSum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        // Traverse the right subtree
        convertBST(root.right);
        // Process the current node
        cumulativeSum += root.val;
        root.val = cumulativeSum;
        // Traverse the left subtree
        convertBST(root.left);
        return root;
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the BST. This is because we are traversing each node exactly once.

Space Complexity

The space complexity is O(h), where h is the height of the tree. This is due to the recursion stack used for the depth-first search. In the worst case of a highly imbalanced tree (e.g., a straight line), the space complexity could be O(n). For a balanced tree, it would be O(log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI