Update BST Based on Rank
Filed under Amazon
Free read 3 of 3Confirm if 'even-ranked' refers to 1-based indexing (2nd, 4th) or 0-based indexing (0th, 2nd).
The question
Given a Binary Search Tree (BST) of student scores, decrement the scores of students at even-ranked positions (1st, 3rd, etc. or 2nd, 4th, etc. depending on definition) by k. The tree structure does not need to be maintained after the update.
Constraints
- Do not use static or global counter variables.
- Do not use pointers passed to recursive calls.
- Tree nodes contain integer scores.
- k is a positive integer.
Examples
- Input
- BST: [10, 5, 15], k=2
- Output
- Modified tree nodes
- Why
- In-order traversal yields [5, 10, 15]. Even ranks (1st: 5, 3rd: 15) are reduced by 2 to [3, 10, 13].
Approach
Confirm if 'even-ranked' refers to 1-based indexing (2nd, 4th) or 0-based indexing (0th, 2nd).
Use standard in-order traversal to visit nodes in sorted order, which corresponds to their rank.
Return a tuple or object from the recursive function containing the updated node and the count of nodes processed so far.
Check if the current rank is even; if so, subtract k from the node's value.
Tips
- What they are testing: Tests ability to manage state in recursion without global variables; consider using a return value that carries the updated node and the current rank count.
- Common mistake: Attempting to use a class-level variable to track rank, which violates the constraint against static/shared state.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.