538. Convert BST to Greater Tree #

Problem #

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

Note: This question is the same as 1038:  https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Example 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]

Example 3:

Input: root = [1,0,2]
Output: [3,3,2]

Example 4:

Input: root = [3,2,4,1]
Output: [7,9,4,10]

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 104 <= Node.val <= 104
• All the values in the tree are unique.
• root is guaranteed to be a valid binary search tree.

Problem Summary #

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

As a reminder, a binary search tree satisfies the following 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.

Solution Approach #

• Based on the ordered property of a binary search tree, to convert it to a Greater Sum Tree, simply traverse in the order of right node - root node - left node and accumulate the sum.
• This problem is the same as Problem 1038.

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func convertBST(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	sum := 0
	dfs538(root, &sum)
	return root
}

func dfs538(root *TreeNode, sum *int) {
	if root == nil {
		return
	}
	dfs538(root.Right, sum)
	root.Val += *sum
	*sum = root.Val
	dfs538(root.Left, sum)
}