Decrease even rank nodes in BST and find minimum in rotated array
Filed under Amazon
Free read 1 of 3Perform a standard inorder traversal (Left-Root-Right) to visit nodes in ascending order of their values.
The question
Given a Binary Search Tree (BST) and an integer 'k', modify the tree by decreasing the value of every node with an even rank by 'k'. The rank of a node is its position in the sorted sequence of all node values (1-indexed).
Constraints
- The BST contains unique integer values.
- k >= 0
- 1 <= Number of nodes <= 10^4
Examples
- Input
- root = [2, 1, 3], k = 1
- Output
- [2, 1, 2]
- Why
- Sorted values: 1 (rank 1), 2 (rank 2), 3 (rank 3). Rank 2 is even, so node 2 becomes 2 - 1 = 1. Wait, the example output is [2, 1, 2] if rank 2 is modified.
Approach
Perform a standard inorder traversal (Left-Root-Right) to visit nodes in ascending order of their values.
Maintain a global or nonlocal counter that increments with every node visited during the traversal.
For each node, check if the current counter (rank) is even. If so, subtract k from the node's value.
Modify the node values directly during the traversal to satisfy the in-place requirement.
Tips
- What they are testing: Dry run with a skewed tree (linked list) and a perfectly balanced tree to ensure rank calculation is correct.
- Common mistake: Confusing rank with tree depth or level; rank is strictly based on the sorted order of values.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.