Convert BST to Greater Tree

Problem Id: 538 Difficulty: Medium Tag: Tree


Intuition

The sum of all keys greater or equal to a node is the sum of all nodes minues the sum all keys less than the node. So we could use 2 inorder traversal to solve this problem.

In the first traversal, we calculate the sum of all nodes. In the second traversal, we keep the sum of all previous visited nodes, and update it to the total_sum - previous_sum.

Solution


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

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        self.total_sum = 0
        self.previous_sum = 0
        self._inorder1(root)
        self._inorder2(root)
        return root

    def _inorder1(self, node):
        if node is None:
            return
        self._inorder1(node.left)
        self.total_sum += node.val
        self._inorder1(node.right)

    def _inorder2(self, node):
        if node is None:
            return
        self._inorder2(node.left)
        tmp = node.val
        node.val = self.total_sum - self.previous_sum
        self.previous_sum += tmp
        self._inorder2(node.right)