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.

Practice

1. You are given a binary search tree and a key. You need to remove the node with this key while maintaining the BST property. Which approach guarantees the correct and efficient deletion in all cases, including nodes with two children?

easy

A. Use a greedy approach that always deletes the node by replacing it with its left child, ignoring the right subtree.

B. Perform a breadth-first traversal to find and remove the node, then rebuild the tree from scratch.

C. Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor.

D. Use dynamic programming to store subtrees and delete nodes based on precomputed results.

Solution

1. Step 1: Understand BST deletion cases

   Deletion must handle three cases: leaf node, node with one child, and node with two children. The two children case requires replacing the node with its in-order successor or predecessor to maintain BST properties.

2. Step 2: Identify approach that handles all cases correctly

   The recursive approach that finds the node, replaces it with its in-order successor if it has two children, and recursively deletes the successor ensures correctness and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only Use a recursive approach that finds the node, then if it has two children, replace it with its in-order successor and recursively delete the successor. correctly handles all deletion cases preserving BST [OK]

Hint: Two-children deletion requires successor replacement [OK]

Common Mistakes:

• Greedy deletion ignoring right subtree breaks BST
• Rebuilding tree is inefficient
• Dynamic programming irrelevant here

2. You are given a binary search tree and asked to find the kth smallest element efficiently without traversing the entire tree. Which approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Perform a full inorder traversal to collect all elements in a list, then return the kth element from the list.

B. Use an iterative inorder traversal with a stack, stopping as soon as the kth smallest element is found.

C. Apply a greedy approach by always moving to the left child until k steps are taken.

D. Use dynamic programming to store counts of nodes in subtrees and then navigate to the kth element.

Solution

1. Step 1: Understand the problem constraints

   We want to find the kth smallest element in a BST efficiently, avoiding unnecessary traversal.

2. Step 2: Evaluate approaches

   Full inorder traversal (A) is correct but not optimal since it traverses the entire tree. Greedy left moves (C) fail because the kth element may not be in the leftmost path. DP (D) is complex and not standard for this problem. Iterative inorder with early stopping (B) visits only needed nodes, achieving O(H + k) time and O(H) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative inorder with early stopping avoids full traversal [OK]

Hint: Early stopping in inorder traversal is optimal [OK]

Common Mistakes:

• Assuming full traversal is necessary
• Confusing greedy left moves with inorder traversal

3. Consider the following buggy code for deleting a node in a BST. Which line contains the subtle bug that can cause the BST property to break when deleting a node with two children?

def deleteNode(root, key):
    if not root:
        return null
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            successor = findSuccessor(root)
            root.val = successor.val
            root.left = deleteNode(root.right, successor.val)  # Bug here
    return root

medium

A. Line where root.left is assigned deleteNode(root.right, successor.val)

B. Line where root.left is assigned deleteNode(root.left, key)

C. Line where root.val is set to successor.val

D. Line where root.right is assigned deleteNode(root.right, key)

Solution

1. Step 1: Identify two-children deletion logic

   When deleting a node with two children, we replace its value with the successor's value and then delete the successor from the right subtree.

2. Step 2: Spot incorrect subtree assignment

   The line assigns root.left = deleteNode(root.right, successor.val), which incorrectly deletes from the right subtree but assigns result to left child, breaking BST structure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct line should assign root.right = deleteNode(root.right, successor.val) [OK]

Hint: Deleting successor must update right subtree, not left [OK]

Common Mistakes:

• Mixing left and right subtree assignments
• Forgetting to update parent's child pointer
• Replacing value but not deleting successor

4. The following code attempts to find the lowest common ancestor in a BST. Identify the bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

medium

A. Line 3: Using '<=' and '>=' instead of '<' and '>' causes incorrect ancestor detection.

B. Line 6: Returning current too early without checking if current matches p or q.

C. Line 4: Not handling null root before loop causes crash on empty tree.

D. Line 5: Moving current to left or right without verifying if child exists causes errors.

Solution

1. Step 1: Analyze comparison operators

   Using '<=' and '>=' causes the loop to move past the node when p or q equals current, missing the case where current is ancestor of itself.

2. Step 2: Correct operator usage

   Changing to '<' and '>' ensures the loop stops at the correct ancestor node, including when one node is ancestor of the other.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive comparisons skip valid ancestor nodes [OK]

Hint: Use strict inequalities to detect ancestor nodes correctly [OK]

Common Mistakes:

• Assuming ancestor must be strictly above nodes
• Ignoring null root edge cases
• Returning too early without validation

5. Suppose the BST can contain duplicate values and you want to find the kth smallest element counting duplicates as separate elements. Which modification to the iterative inorder traversal approach correctly handles duplicates without extra space or preprocessing?

hard

A. Perform a full inorder traversal collecting all values, then remove duplicates before indexing kth element.

B. Modify the traversal to skip nodes with duplicate values to avoid counting duplicates multiple times.

C. Use a hash set to track visited values and only increment count for unique values.

D. Keep the traversal unchanged; duplicates are naturally counted separately in inorder traversal order.

Solution

1. Step 1: Understand duplicates in BST inorder traversal

   Inorder traversal visits nodes in sorted order including duplicates as separate nodes.

2. Step 2: Check if modification is needed

   Since duplicates appear as separate nodes, counting each node visited naturally counts duplicates separately without extra logic.

3. Step 3: Evaluate other options

   Skipping duplicates (B) or using a hash set (C) changes semantics. Removing duplicates after full traversal (D) is inefficient and breaks counting duplicates separately.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Inorder traversal inherently counts duplicates separately [OK]

Hint: Duplicates appear as separate nodes in inorder traversal [OK]

Common Mistakes:

• Trying to skip duplicates
• Using extra space unnecessarily
• Assuming duplicates must be merged