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. Given the following code snippet for converting a sorted array to a height-balanced BST, what is the value of the root node's value after the first call to helper with input nums = [1, 3, 5]?

easy

A. 3

B. 1

C. 5

D. None

Solution

1. Step 1: Calculate mid index for initial call

   For nums=[1,3,5], left=0, right=2, mid=(0+2)//2=1.

2. Step 2: Identify root value

   nums[mid] = nums[1] = 3, so root node value is 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mid index calculation picks 3 as root [OK]

Hint: Mid index picks middle element as root [OK]

Common Mistakes:

• Choosing first or last element as root
• Off-by-one mid calculation

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 snippet for converting a sorted array to a height-balanced BST. Which line contains the subtle bug that can cause infinite recursion or stack overflow?

medium

A. Line 5: left_child = self.helper(nums, left, mid - 1)

B. Line 3: mid = (left + right) // 2

C. Line 7: root.right = self.helper(nums, mid + 1, right)

D. Line 2: if left >= right: return None

Solution

1. Step 1: Understand base case condition

   The base case should be when left > right, not left >= right, to allow single-element subarrays.

2. Step 2: Consequence of incorrect base case

   Using left >= right causes the recursion to skip processing subarrays of size 1, leading to infinite recursion or missing nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case must allow left == right to process single elements [OK]

Hint: Base case must be left > right, not left >= right [OK]

Common Mistakes:

• Incorrect base case causing infinite recursion
• Misplaced mid calculation

4. What is the worst-case time complexity of inserting a value into a binary search tree using the iterative insertion method shown below?

def insertIntoBST(root, val):
    if root is None:
        return TreeNode(val)
    curr = root
    while curr:
        if val < curr.val:
            if curr.left is None:
                curr.left = TreeNode(val)
                return root
            curr = curr.left
        else:
            if curr.right is None:
                curr.right = TreeNode(val)
                return root
            curr = curr.right
    return root

medium

A. O(1) because insertion is done at a leaf immediately

B. O(h) where h is the height of the tree, since traversal down the tree is needed

C. O(n) where n is the number of nodes, because all nodes might be visited

D. O(log n) always, because BSTs are balanced by definition

Solution

1. Step 1: Identify traversal cost

   Insertion requires traversing from root down to a leaf where the new node is inserted.

2. Step 2: Relate traversal to tree height

   In worst case, the tree is skewed, so height h can be up to n, but complexity is expressed as O(h).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Traversal cost dominates insertion -> O(h) [OK]

Hint: Insertion cost depends on tree height, not always balanced [OK]

Common Mistakes:

• Assuming O(1) because insertion is at leaf
• Confusing height h with number of nodes n
• Assuming BST is always balanced

5. What is the time complexity of the iterative inorder traversal approach to find the kth smallest element in a BST, where H is the height of the tree and k is the input parameter?

medium

A. O(H + k), where H is the height of the tree and k is the kth element to find

B. O(k), since only k nodes are visited

C. O(k log n), assuming balanced BST

D. O(n), where n is the total number of nodes in the BST

Solution

1. Step 1: Analyze traversal steps

   The algorithm traverses down to the leftmost node (cost O(H)) and then visits k nodes in inorder sequence.

2. Step 2: Combine costs

   Total time is O(H) to reach leftmost node plus O(k) to visit k nodes, so O(H + k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal cost depends on height plus k nodes visited [OK]

Hint: Traversal cost includes height plus k nodes visited [OK]

Common Mistakes:

• Assuming O(n) always
• Ignoring height cost
• Assuming only k nodes visited without stack overhead