Last updated on July 18th, 2024 at 10:14 pm
Here, We see Convert BST to Greater Tree LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Tree
Companies
Amazon
Level of Question
Medium
![Convert BST to Greater Tree LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Convert BST to Greater Tree LeetCode Solution
Table of Contents
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.
As a reminder, a binary search tree is a tree that satisfies these constraints:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
![tree](https://i0.wp.com/assets.leetcode.com/uploads/2019/05/02/tree.png?w=1400&ssl=1)
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Example 2:
Input: root = [0,null,1]
Output: [1,null,1]
1. Convert BST to Greater Tree LeetCode Solution C++
class Solution { public: TreeNode* convertBST(TreeNode* root) { int num = 0; solve(root, num); return root; } void solve(TreeNode *root, int &num) { if(root == NULL) return; solve(root->right, num); root->val = num + root->val; num = root->val; solve(root->left, num); } };
2. Convert BST to Greater Tree Solution Java
class Solution { int sum = 0; public TreeNode convertBST(TreeNode root) { if(root==null){ return root; } reverseInorder(root); return root; } private void reverseInorder(TreeNode root){ if(root==null){ return; } reverseInorder(root.right); root.val = root.val + sum; sum = root.val; reverseInorder(root.left); return; } }
3. Convert BST to Greater Tree Solution JavaScript
var convertBST = function(root) { let sum = 0, prev = 0; function rec(root){ if(root){ rec(root.right); sum += root.val; root.val += prev; prev = sum; rec(root.left); } } rec(root); return root; }
4. Convert BST to Greater Tree Solution Python
class Solution(object): def convertBST(self, root): def dfs(node): if node: dfs(node.right) node.val += dfs.greater_sum dfs.greater_sum = node.val dfs(node.left) dfs.greater_sum = 0 dfs(root) return root