##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/538.html

# 538. Convert BST to Greater Tree

Easy

## Description

Given 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 sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
5
/   \
2     13

Output: The root of a Greater Tree like this:
18
/   \
20     13

## Solution

Same but just left/right mirror of https://leetcode.ca/2016-03-03-94-Binary-Tree-Inorder-Traversal

Begin by obtaining the inorder traversal of the binary search tree. This traversal lists all the nodes of the tree in ascending order based on their values.

Next, iterate over the inorder traversal in reverse order, skipping the last node (which corresponds to the highest value node in the original tree). For each node, find its immediate successor in the inorder traversal (i.e., the next node in the forward direction) and add its value to the node’s own value. After this operation, the node’s value will be updated to its original value plus the sum of all values greater than its own value in the original tree.

Finally, return the modified root node of the binary search tree.

• public class Convert_BST_to_Greater_Tree {
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

int sum = 0;

public TreeNode convertBST(TreeNode root) {
if (root == null) {
return null;
}

convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);

return root;
}
}
}

############

/**
* Definition for a binary tree node.
* public 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;
*     }
* }
*/
class Solution {
public TreeNode convertBST(TreeNode root) {
int s = 0;
TreeNode node = root;
while (root != null) {
if (root.right == null) {
s += root.val;
root.val = s;
root = root.left;
} else {
TreeNode next = root.right;
while (next.left != null && next.left != root) {
next = next.left;
}
if (next.left == null) {
next.left = root;
root = root.right;
} else {
s += root.val;
root.val = s;
next.left = null;
root = root.left;
}
}
}
return node;
}
}

• // OJ: https://leetcode.com/problems/convert-bst-to-greater-tree/
// Time: O(N)
// Space: O(H)
class Solution {
int sum = 0;
public:
TreeNode* convertBST(TreeNode* root) {
if (!root) return nullptr;
convertBST(root->right);
root->val = (sum += root->val);
convertBST(root->left);
return root;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# same but just left/right mirror of https://leetcode.ca/2016-03-03-94-Binary-Tree-Inorder-Traversal/
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = []
current = root
s = 0 # sum
while stack or current:
while current:
stack.append(current)
current = current.right

right_or_middle = stack.pop()
s += right_or_middle.val
right_or_middle.val = s

current = right_or_middle.left

return root

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def __init__(self):
self.lSum = 0

def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return None
self.convertBST(root.right)
self.lSum += root.val
root.val = self.lSum
self.convertBST(root.left)
return root

• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func convertBST(root *TreeNode) *TreeNode {
s := 0
node := root
for root != nil {
if root.Right == nil {
s += root.Val
root.Val = s
root = root.Left
} else {
next := root.Right
for next.Left != nil && next.Left != root {
next = next.Left
}
if next.Left == nil {
next.Left = root
root = root.Right
} else {
s += root.Val
root.Val = s
next.Left = nil
root = root.Left
}
}
}
return node
}

•