Convert BST to Greater Tree

1. Problem Description

Given the root of a binary search tree whose node values are distinct, convert it to a Greater Sum Tree so that the new value of each node equals the sum of all values in the original tree that are greater than or equal to node.val.

2. Approach

1. Approach 1
   • Convert the inorder traversal to an array
   • Accumulate backward from the last element
2. Approach 2
   • Traverse inorder in reverse
   • Essentially similar to Kth Node in a Binary Search Tree

3. Implementation

3.1. Convert Inorder Traversal to an Array

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
	path := make([]*TreeNode, 0)
	convertBSTDFS(root, &path)
	for i := len(path) - 2; i >= 0; i-- {
		path[i].Val += path[i+1].Val
	}
	return root
}

func convertBSTDFS(root *TreeNode, path *[]*TreeNode) {
	if root == nil {
		return
	}

	convertBSTDFS(root.Left, path)
	*path = append(*path, root)
	convertBSTDFS(root.Right, path)
}

3.2. Reverse Inorder Traversal

//**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    dfs(root, &sum)
    return root
}

func dfs(root *TreeNode, sum *int) {
    if root == nil {
        return
    }

    dfs(root.Right, sum)
    *sum += root.Val
    root.Val = *sum
    dfs(root.Left, sum)
}

4. References

• 538. Convert BST to Greater Tree - LeetCode