Dare2Solve
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.
dfs
to perform the reverse in-order traversal and update the node values.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.
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) ).
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int sum = 0;
function<void(TreeNode*)> dfs = [&](TreeNode* node) {
if (!node) return;
dfs(node->right);
sum += node->val;
node->val = sum;
dfs(node->left);
};
dfs(root);
return root;
}
};
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
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);
}
}
/**
* @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;
};