grid47 Exploring patterns and algorithms
Sep 14, 2024
5 min read
Solution to LeetCode 538: Convert BST to Greater Tree Problem
Given the root of a Binary Search Tree (BST), convert it into a Greater Tree where every node’s value is replaced by the sum of all greater node values in the BST plus its original value.
Problem
Approach
Steps
Complexity
Input: Each input consists of a binary search tree represented by its root. The nodes of the tree contain integer values.
Example: Input: root = [5, 2, 13]
Constraints:
• The number of nodes in the tree is in the range [0, 10^4].
• Each node value is an integer within the range [-10^4, 10^4].
• All node values are unique.
Output: Return the root of the binary search tree after transforming it into the Greater Tree.
Example: Output: [18, 20, 13]
Constraints:
• The output should be a valid Binary Search Tree where each node’s value is the sum of all greater node values plus its original value.
Goal: Transform the BST into a Greater Tree by updating each node's value.
Steps:
• Perform a reverse inorder traversal (right, node, left) to access nodes in descending order.
• Accumulate the sum of node values greater than the current node’s value.
• Update the current node's value by adding the accumulated sum.
Goal: The input tree must be a valid binary search tree (BST) with unique values.
Steps:
• The tree is a valid BST.
• The values of the nodes are unique.
• The tree contains between 0 and 10^4 nodes.
Assumptions:
• The input tree is a valid Binary Search Tree.
• Input: Input: root = [5, 2, 13]
• Explanation: In this example, after transforming the BST into a Greater Tree, the node with value 5 becomes 18, the node with value 2 becomes 20, and the node with value 13 stays the same.
Approach: To solve this problem, we need to traverse the BST in descending order and update each node’s value with the sum of all greater node values.
Observations:
• We can solve this problem efficiently by using a reverse inorder traversal of the BST.
• In reverse inorder traversal, we visit the right child first, then the node itself, followed by the left child. This way, we encounter the largest nodes first.
Steps:
• Initialize a global variable to keep track of the cumulative sum of the values of the nodes visited.
• Perform reverse inorder traversal: first visit the right child, then the node, and finally the left child.
• For each node, add the cumulative sum to its value and update the cumulative sum.
Empty Inputs:
• If the input tree is empty, return null.
Large Inputs:
• Ensure that the solution can handle trees with up to 10^4 nodes.
Special Values:
• Handle trees with negative node values correctly.
Constraints:
• The tree is guaranteed to be a valid binary search tree.
classSolution {
int sum =0;
public:TreeNode* convertBST(TreeNode* root) {
convert(root);
return root;
}
voidconvert(TreeNode* root) {
if(!root) return;
convert(root->right);
root->val += sum;
sum = root->val;
convert(root->left);
}
1 : Class Definition
classSolution {
Defines the `Solution` class which will contain the method to convert a BST to a Greater Tree.
2 : Variable Initialization
int sum =0;
Declares an integer variable `sum` and initializes it to 0. This variable will store the cumulative sum during the traversal.
3 : Access Modifier
public:
Indicates the start of the public access modifier, making the following methods accessible from outside the class.
4 : Function Definition
TreeNode*convertBST(TreeNode* root) {
Defines the `convertBST` method which takes the root of a Binary Search Tree as input and returns the root of the converted Greater Tree.
5 : Function Call
convert(root);
Calls the private helper method `convert` to perform the conversion on the BST.
6 : Return Statement
return root;
Returns the root of the modified BST (now a Greater Tree) after the conversion.
7 : Function Definition
voidconvert(TreeNode* root) {
Defines the helper method `convert`, which is used to recursively traverse the tree and accumulate the sum of node values.
8 : Base Case
if(!root) return;
Checks if the current node is null. If so, the function returns without doing anything.
9 : Recursive Call
convert(root->right);
Recursively calls the `convert` method on the right subtree to process all nodes in the right subtree first (reverse inorder traversal).
10 : Node Value Update
root->val += sum;
Adds the current value of `sum` to the node's value. This ensures each node's value is updated with the cumulative sum of all greater nodes.
11 : Sum Update
sum = root->val;
Updates the `sum` variable to the current node's value, so it can be used by subsequent nodes in the traversal.
12 : Recursive Call
convert(root->left);
Recursively calls the `convert` method on the left subtree to process all nodes in the left subtree after updating the current node.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we perform a single traversal of the tree, visiting each node once.
Best Case: O(h)
Worst Case: O(h)
Description: The space complexity is O(h), where h is the height of the tree. This accounts for the recursive stack in a depth-first traversal.
