Convert BST to Greater Tree

📋

Problem

Imagine you have a database of user scores stored in a BST, and you want to update each score to reflect the sum of all scores greater than or equal to it, to quickly answer ranking queries.

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 the BST. Return the root of the modified tree.

The number of nodes in the tree is in the range [1, 10^5].0 <= Node.val <= 10^4The given tree is a valid binary search tree.

Edge cases: Single node tree → node value remains the sameAll nodes have the same value → each node updated to value * number of nodesRight skewed tree → values accumulate from bottom to top

</>

IDE

def convertBST(root: Optional[TreeNode]) -> Optional[TreeNode]:public TreeNode convertBST(TreeNode root)TreeNode* convertBST(TreeNode* root)function convertBST(root)

def convertBST(root):
    # Write your solution here
    pass

class Solution {
    public TreeNode convertBST(TreeNode root) {
        // Write your solution here
        return root;
    }
}

#include <vector>
using namespace std;

TreeNode* convertBST(TreeNode* root) {
    // Write your solution here
    return root;
}

function convertBST(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Original node values unchangedNo traversal or accumulation performed; returns input tree as is.✅ Implement reverse inorder traversal updating node values with cumulative sums.

Wrong: Node values updated with sum of all nodes (not just greater)Summing all nodes instead of only greater nodes during update.✅ Accumulate sums only from nodes with values greater than current node during reverse inorder traversal.

Wrong: Incorrect values due to off-by-one in cumulative sum updateUpdating node value before adding its original value to cumulative sum.✅ Add node's original value to cumulative sum before updating node.val.

Wrong: Fails on single node or empty tree with errors or wrong outputNo base case handling for null or single node trees.✅ Add base case checks for null nodes and handle single node trees correctly.

Wrong: TLE on large inputsUsing O(n^2) brute force approach summing greater nodes repeatedly.✅ Use O(n) reverse inorder traversal with cumulative sum to avoid repeated summations.

✓

Test Cases

Focus on handling minimal and uniform trees correctly before tackling edge cases.

Review traversal order and sum accumulation to avoid common algorithmic pitfalls.

Ensure your solution runs in linear time to handle large inputs efficiently.

t1_01basic

Input{"root":[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]}

Expected[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

⏱ Performance - must finish in 2000ms

Traverse the BST in reverse inorder (right-root-left), accumulate the sum of visited nodes, and update each node's value to this sum.

💡 Think about traversing the tree in reverse inorder to accumulate sums.

💡 Use a running total to update each node's value during traversal.

💡 Implement a reverse inorder traversal (right, root, left) and keep a cumulative sum variable.

Why it failed: Failed to accumulate sums correctly in reverse inorder traversal; fix by maintaining a global or external cumulative sum updated during traversal.

✓ Correctly accumulates and updates node values using reverse inorder traversal.

t1_02basic

Input{"root":[2,0,3,null,1]}

Expected[5,6,3,null,6]

⏱ Performance - must finish in 2000ms

Reverse inorder traversal updates nodes: 3→3, 2→5 (3+2), 1→6 (3+2+1), 0→6 (3+2+1+0).

💡 Try reverse inorder traversal to accumulate sums from largest to smallest.

💡 Keep track of cumulative sum and update each node's value accordingly.

💡 Update node.val += cumulative sum of all previously visited nodes with greater values.

Why it failed: Incorrect node values due to missing or incorrect cumulative sum update; fix by updating cumulative sum after visiting right subtree and before left subtree.

✓ Correctly updates all nodes with accumulated sums in reverse inorder.

t2_01edge

Input{"root":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node tree remains unchanged as no greater nodes exist.

💡 Consider what happens when the tree has only one node.

💡 No nodes have greater values, so the node's value stays the same.

💡 Ensure your code handles single-node trees without errors.

Why it failed: Fails single node case by altering node value incorrectly; fix by ensuring cumulative sum starts at zero and updates only after visiting nodes.

✓ Handles single node tree correctly with no value changes.

t2_02edge

Input{"root":[2,2,2]}

Expected[6,6,6]

⏱ Performance - must finish in 2000ms

All nodes have value 2; cumulative sums update all nodes to 6 (2+2+2) because sum includes equal values.

💡 Test how your code handles nodes with identical values.

💡 Remember that only strictly greater values contribute to the sum.

💡 Adjust logic to include equal values if problem states 'greater or equal' or only strictly greater if not.

Why it failed: Incorrect handling of equal values; fix by clarifying if sum includes equal values and adjusting comparison accordingly.

✓ Correctly handles trees with identical node values.

t2_03edge

Input{"root":[1,null,2,null,3,null,4]}

Expected[10,null,9,null,7,null,4]

⏱ Performance - must finish in 2000ms

Right skewed tree accumulates sums from bottom to top: 4→4, 3→7, 2→9, 1→10.

💡 Consider how a right skewed tree affects traversal order.

💡 Reverse inorder traversal visits nodes from largest to smallest.

💡 Ensure cumulative sum updates correctly as you traverse down the right spine.

Why it failed: Fails right skewed tree by incorrect traversal order; fix by implementing reverse inorder traversal visiting right child first.

✓ Correctly accumulates sums in right skewed tree.

t3_01corner

Input{"root":[5,2,13]}

Expected[18,20,13]

⏱ Performance - must finish in 2000ms

Greedy approach fails; correct reverse inorder accumulates sums: 13→13, 5→18, 2→20.

💡 Beware of greedy approaches that update nodes without considering all greater nodes.

💡 Use reverse inorder traversal to accumulate sums correctly.

💡 Maintain a cumulative sum variable updated after visiting right subtree.

Why it failed: Greedy approach fails by updating nodes prematurely; fix by using reverse inorder traversal with cumulative sum updated after right subtree.

✓ Correctly handles greedy trap by proper traversal and accumulation.

t3_02corner

Input{"root":[3,1,4,null,2]}

Expected[7,8,4,null,6]

⏱ Performance - must finish in 2000ms

Confusion between 0/1 knapsack and unbounded; here, each node updated once with sum of greater nodes.

💡 Each node is updated once; no repeated counting like unbounded knapsack.

💡 Reverse inorder traversal accumulates sums without revisiting nodes.

💡 Avoid double counting values by updating nodes in one pass.

Why it failed: Incorrectly accumulates sums multiple times per node; fix by updating each node exactly once during reverse inorder traversal.

✓ Correctly updates each node once with accumulated sums.

t3_03corner

Input{"root":[10,5,15,2,7,null,20]}

Expected[48,37,35,47,40,null,20]

⏱ Performance - must finish in 2000ms

Off-by-one errors in cumulative sum cause incorrect node values; correct sums: 20→20, 15→35, 10→48, 7→40, 5→37, 2→47.

💡 Check if cumulative sum is updated before or after node value update.

💡 Ensure cumulative sum includes current node's original value before updating.

💡 Update node.val with cumulative sum after adding current node's original value.

Why it failed: Off-by-one error in sum update order; fix by adding node's original value to cumulative sum before updating node.val.

✓ Correctly handles cumulative sum update order avoiding off-by-one errors.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875,1562,4687,7812,10937,14062,17187,20312,23437,26562,29687,32812,35937,39062,42187,45312,48437,51562,54687,57812,60937,64062,67187,70312,73437,76562,79687,82812,85937,89062,92187,95312,98437,781,2343,3906,5468,7031,8593,10156,11718,13281,14843,16406,17968,19531,21093,22656,24218,25781,27343,28906,30468,32031,33593,35156,36718,38281,39843,41406,42968,44531,46093,47656,49218,50781,52343,53906,55468,57031,58593,60156,61718,63281,64843,66406,67968,69531,71093,72656,74218,75781,77343,78906,80468,82031,83593,85156,86718,88281,89843,91406,92968,94531,96093,97656,99218]}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced BST with 127 nodes (complete tree of height 7) to test O(n) complexity; must complete within 2 seconds.

💡 Use O(n) reverse inorder traversal to accumulate sums efficiently.

💡 Avoid repeated summations or nested traversals that cause O(n^2) time.

💡 Maintain a cumulative sum variable updated during traversal to achieve linear time.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing reverse inorder traversal with cumulative sum to achieve O(n) time.

✓ Efficient O(n) traversal confirmed by passing performance test.