Add All Greater Values to Nodes in BST
Filed under Amazon
Free read 2 of 3Confirm that the structure is a valid BST and that we should mutate the nodes in place.
The question
Given a Binary Search Tree (BST), modify its nodes such that each node's new value is the original value plus the sum of all values greater than the original node's value in the BST.
Constraints
- The number of nodes in the tree is in the range [1, 100].
- 0 <= Node.val <= 10^4
Examples
- Input
- Root = [4, 1, 6]
- Output
- [10, 15, 6]
- Why
- Values greater than 4 are 6 (sum=10). Values greater than 1 are 4, 6 (sum=15). Values greater than 6 are none (sum=6).
Approach
Confirm that the structure is a valid BST and that we should mutate the nodes in place.
For each node, perform a traversal to collect all values greater than the current node's value and sum them up. Time complexity is O(N^2).
Perform a reverse in-order traversal, keeping a running sum of all visited nodes so far, and add this running sum to the current node. Time complexity is O(N).
Single-node tree, skewed tree (left-heavy or right-heavy).
Solution
O(N) time, O(H) space
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
self.total = 0
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right)
self.total += node.val
node.val = self.total
reverse_inorder(node.left)
reverse_inorder(root)
return root
Tips
- What they are testing: Tests reverse in-order traversal (Right -> Root -> Left) to process nodes in descending order.
- Common mistake: Using a standard in-order traversal which visits nodes in ascending order, failing to accumulate larger values correctly.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.