538. Convert BST to Greater Tree Medium

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

Example 1:
Input: [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]

Approach

Input: The root node of a binary search tree root

Output: Convert it to a Greater Tree and return it

This problem belongs to Binary Search Tree + Reverse Inorder Traversal problems.

Binary Search Tree (BST) characteristics: Right subtree value > current node value > Left subtree value.

So the key point is to accumulate starting from the maximum value, which is essentially starting from the rightmost value, so we must traverse from right to left, meaning a Reverse Inorder Traversal (Right -> Node -> Left).

Because we need to repeatedly accumulate and need to record the last value, we can use a global variable total to record.

We first traverse to the maximum value node through dfs(node.right). Then during the "return" phase, we start accumulating total += node.val which makes the current node's value the accumulated one.

Then we recurse dfs(node.left) where we can accumulate directly during the traversal process. That is, during the "pass down" phase we just keep accumulating total += node.val, which becomes the accumulated value for the current node.

Finally, directly returning the root node is the answer, so it's a typical recursion problem with both pass-down and return-up steps.

Implementation

python

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        total = 0  # Initialize a global variable to record the accumulated sum of visited nodes

        def dfs(node):
            nonlocal total  # Use the external total variable, allowing modification within recursion

            if not node:
                return  # Return directly for an empty node, no processing needed

            # First recursively visit the right subtree (right subtree node values are larger, ensuring larger values are processed first)
            dfs(node.right)

            # Process the current node: add the current node value to total, and update the node value to the accumulated sum
            total += node.val  # Add current node value to total (includes the current node's value)
            node.val = total   # Update the node value to total (sum of values greater than or equal to current node's value)

            # Then recursively visit the left subtree (left subtree node values are smaller, continue accumulating)
            dfs(node.left)

        dfs(root)  # Process the whole tree starting from the root node
        return root  # Return the root node of the converted Greater Tree

javascript

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    let total = 0;

    function dfs(node) {
        if (!node) return;

        dfs(node.right);

        total += node.val;
        node.val = total;

        dfs(node.left);
    }

    dfs(root);

    return root;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

538. Convert BST to Greater Tree (English)

538. 把二叉搜索树转换为累加树 (Chinese)