Convert BST to Greater Tree

Problem

Transform a BST so each node value becomes the sum of all original values greater than or equal to it. Return the new root.

Constraints

• 0 ≤ nodes ≤ 10⁴

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def convertBST(self, root):
        total = 0
        def dfs(node):
            nonlocal total
            if not node:
                return
            dfs(node.right)
            total += node.val
            node.val = total
            dfs(node.left)
        dfs(root)
        return root

Java

class Solution {
    public TreeNode convertBST(TreeNode root) {
        int[] running = {0};
        walk(root, running);
        return root;
    }
    private void walk(TreeNode n, int[] running) {
        if (n == null) return;
        walk(n.right, running);
        running[0] += n.val;
        n.val = running[0];
        walk(n.left, running);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.