Leetcode 538. Convert BST to Greater Tree
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.
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:
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;
}
}
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.
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).
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?