The blog for Design Patterns, Linux, HA and Myself!

05
September 2020

In this article, we’ll be solving the problem: Convert BST to Greater Tree.
Just like the problems, Univalued Binary Tree and Leaf Similar Trees
this problem belongs to **Tree Traversal** and **Recursion** category.

` ````
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
```

The provided tree will always be a Binary Search Tree(BST). This means that if we traverse the elements from right to left we’ll be traversing it in a decreasing order. For example, if the tree is:

then we’ll get 13, 12, 11, 10, 9, 8 (in that order) if we traverse from right to left. This order is decreasing order. We’ll use this tree traversal approach to solve this problem. We’ll first visit the right child of a node, then the node itself and then the left child of the node. This way, we’ll go to 13 then to 12 then to 11 and so on.

Along with traversing the nodes, we’ll update the node value by adding the value of the previous node as well. For example, we’ll go to 13, then to 12, here we’ll update the value to 25(12 + 13) and pass this value to 11. At 11, we’ll update the value to 36(11 + 25) traverse to 10.

This image shows the updated tree once the traversal is complete.

This way we’ve converted the tree to a Greater Tree. Here is the program for it:

```
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func convertBST(root *TreeNode) *TreeNode {
rightOrder(root, 0)
return root
}
func rightOrder(node *TreeNode, valueToAdd int) int {
if node == nil {
return 0
}
if node.Right != nil {
valueToAdd = rightOrder(node.Right, valueToAdd)
}
node.Val += valueToAdd
valueToAdd = node.Val
if node.Left != nil {
return rightOrder(node.Left, valueToAdd)
}
return valueToAdd
}
```

This is available @ GitHub as well.

Loading Comments...

- All Elements in Two Binary Search Trees Solution
- Construct Binary Search Tree From Preorder Traversal Solution
- Maximum Binary Tree Solution
- Sum of Nodes With Even Valued Grandparent Solution
- Deepest Leaves Sum Solution
- Symmetric Tree or Mirror Tree Solution
- Diameter of Binary Tree Solution
- Binary Tree Paths Solution
- Cousins in Binary Tree Solution
- Sum of Left Leaves Solution
- Same Tree or Equal Tree Solution
- Minimum Absolute Difference in BST Solution
- Construct String From Binary Tree Solution - Leetcode
- Two Sum IV - Input is a BST Solution - Leetcode
- Convert BST to Greater Tree Solution - Leetcode
- Convert Sorted Array to Binary Search Tree Solution
- Average of Levels in Binary Tree Solution
- Leaf Similar Trees Solution - Leetcode
- Sum of Root to Leaf Binary Numbers - Leetcode
- Univalued Binary Tree - Leetcode
- Maximum Depth of N Ary Tree - Leetcode
- Increasing Order Search Tree - Leetcode
- Merge Two Binary Trees Solution
- Range Sum of BST - Leetcode