
Intuition
The goal is to transform the given Binary Search Tree (BST) such that each node's value is updated to be the original node value plus the sum of all node values greater than the original node value. To achieve this, we can leverage the properties of the BST and perform a reverse in-order traversal (right-root-left). During this traversal, we maintain a running sum of all visited nodes, which allows us to update each node's value correctly.
Approach
- Reverse In-order Traversal: The key idea is to traverse the BST in a reverse in-order manner. This means we process the right subtree first, then the current node, and finally the left subtree. This traversal ensures that we visit nodes in descending order.
- Running Sum: Maintain a running sum of all node values visited so far. Initialize this sum to 0.
- Update Node Values: As we visit each node during the traversal, add the node's value to the running sum and update the node's value with the running sum.
- Recursive Helper Function: Define a helper function
dfs
to perform the reverse in-order traversal and update the node values.
Steps:
- Start from the root of the BST.
- Traverse the right subtree recursively.
- Update the running sum and the current node's value.
- Traverse the left subtree recursively.
Complexity
Time Complexity
The time complexity of the convertBST
function is \( O(n) \), where \( n \) is the number of nodes in the Binary Search Tree (BST). This is because the function performs a reverse in-order traversal of the BST, visiting each node exactly once.
Space Complexity
The space complexity of the convertBST
function is \( O(h) \), where \( h \) is the height of the BST. This space is primarily used by the recursion stack during the traversal. In the worst case, for a skewed BST where the height \( h \) is \( O(n) \), the space complexity would be \( O(n) \). However, for a balanced BST, the height \( h \) is \( O(log n) \), resulting in a space complexity of \( O(log n) \).
Code
C++
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int sum = 0;
function dfs = [&](TreeNode* node) {
if (!node) return;
dfs(node->right);
sum += node->val;
node->val = sum;
dfs(node->left);
};
dfs(root);
return root;
}
};
Python
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
self.sum = 0
def dfs(node):
if not node:
return
if node.right:
dfs(node.right)
self.sum += node.val
node.val = self.sum
if node.left:
dfs(node.left)
dfs(root)
return root
Java
class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
dfs(root);
return root;
}
private void dfs(TreeNode node) {
if (node == null) return;
dfs(node.right);
sum += node.val;
node.val = sum;
dfs(node.left);
}
}
JavaScript
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var convertBST = function (root) {
var sum = 0;
var dfs = function (node) {
if (!node) return;
dfs(node.right);
sum += node.val;
node.val = sum;
dfs(node.left);
};
dfs(root);
return root;
};