K-th Ranked Ticket

MediumTrees

Problem

A help desk stores ticket numbers (distinct integers) in a binary search tree. The manager wants the ticket with the k-th smallest number (1-indexed).

Return that value.

Example 1

Input:
root = [5, 3, 6, 2, 4, null, null, 1], k = 3
Output:
3

In sorted order the values are 1, 2, 3, 4, 5, 6; the third is 3.

Example 2

Input:
root = [3, 1, 4, null, 2], k = 1
Output:
1

Constraints

  • 1 ≤ k ≤ number of nodes ≤ 10^4
  • 0 ≤ node.val ≤ 10^6
  • All values are distinct.

Hint

Show the first hint

What traversal visits a search tree's values in increasing order?

Walkthrough

How to approach it

01Clarify before coding

  • Is k 1-indexed? Yes, k = 1 is the minimum.
  • Is k always valid? Yes, 1 ≤ k ≤ n.
  • Will this be asked repeatedly on a changing tree? Not here, but it is a common follow-up.

02Brute force

Collect all values, sort them and index k - 1.

Cost: O(n log n) time and O(n) space, ignoring that the tree is already ordered.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.