โ† Amazon questions

Add All Greater Values to Nodes in BST

Filed under Amazon

Free read 2 of 3

Confirm 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

  1. Confirm that the structure is a valid BST and that we should mutate the nodes in place.

Solution

O(N) time, O(H) space

Python
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.