DSA-085 · FOCUSED PRACTICE

Kth Smallest Element in a BST

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 23965 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the kth smallest value in a strict BST, using one-based rank.

Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
The input is already a strict BST; this API does not validate ordering, since a full validation traversal would remove its early-stop cost advantage. Preserve all values and child links.
k must be positive and no larger than the node count. Invalid k, including any positive k on null input, throws IllegalArgumentException without mutation. Values may include both int extremes.

Examples

Input: tree=[3,1,4,null,2], k=2
Output: 2
Inorder values are 1,2,3,4; stop at the second emitted node.
Input: tree=[0,MIN,MAX], k=3
Output: MAX
Values are returned directly, not used as sentinels.
Input: tree=[], k=1
Output: IllegalArgumentException
The rank has no witness.

Before you start

Strict BST global ordering and inorder traversal
Explicit left-spine stacks and output-sensitive work

Recognize the structure

Inorder is sorted only because the input contract guarantees a BST. A stack stores suspended ancestors while descending left; emitting one node consumes one sorted rank.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 153/20,000 characters

Self-review

Can I prove what a pop means in sorted rank order?Can I separate the BST precondition from validation work?Can I state valid-rank and invalid-rank costs separately?

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

What traversal emits BST values in increasing order?

Hint 2

An explicit stack can suspend ancestors while descending left.

Hint 3

Count pops, return on the kth one, and reject if traversal ends first.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Materialize all inorder values

Recursively collect the complete inorder sequence, then validate k and select values[k−1]. The first example materializes 1,2,3,4 even though rank two needs only 1 and 2. The main method keeps only a left-spine frontier and stops as soon as the desired node is emitted.

Improve the baseline

Reject nonpositive k immediately

No traversal or mutable state is needed to reject zero or negative ranks.

Expose the next inorder node

Push current while descending left. When current is null, popping the stack yields the smallest un-emitted node.

Consume one rank or continue right

Decrement remaining. If it becomes zero return the node’s value; otherwise set current=node.right. Exhaustion before zero proves k exceeds size.

Why it is correct

Frontier meaning

The stack holds ancestors whose left work has been entered but whose own value has not yet been emitted; deeper entries have earlier inorder priority.

Rank invariant

After r pops, exactly the first r increasing BST values have been emitted and remaining=k−r. Left-spine descent finds the next value without skipping any predecessor.

Success or justified exception

remaining==0 identifies the kth smallest. If both current and stack empty first, every node was emitted, so no requested rank exists.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    public static final class Node {
        public final int value;
        public Node left, right;
        public Node(int value) { this.value = value; }
    }
    public static int kthSmallest(Node root, int k) {
        if (k <= 0) throw new IllegalArgumentException("k must be positive");
        ArrayDeque<Node> stack = new ArrayDeque<>();
        Node current = root;
        int remaining = k;
        while (current != null || !stack.isEmpty()) {
            while (current != null) { stack.push(current); current = current.left; }
            Node node = stack.pop();
            if (--remaining == 0) return node.value;
            current = node.right;
        }
        throw new IllegalArgumentException("k exceeds node count");
    }
    private static void inorder(Node node, List<Integer> values) {
        if (node == null) return;
        inorder(node.left,values); values.add(node.value); inorder(node.right,values);
    }
    public static int baseline(Node root, int k) {
        if (k <= 0) throw new IllegalArgumentException("k must be positive");
        List<Integer> values = new ArrayList<>(); inorder(root,values);
        if (k > values.size()) throw new IllegalArgumentException("k exceeds node count");
        return values.get(k-1);
    }
}

Read the meaningful blocks

Do not call BST validation internally

Ordering is a declared precondition; adding a full scan changes early-return complexity.

Stack size is not emitted count

Many ancestors may be pending before the first value. remaining changes only when a node is popped for emission.

No threaded mutation is used

The explicit stack avoids Morris traversal’s temporary edges and its restoration hazards under early return.

Complexity

For valid k, time is O(h+k) and auxiliary space O(h), where h is tree height. A skewed BST can have h=n, so this is not an unconditional O(log n+k) bound. Out-of-range positive k costs O(n); k<=0 costs O(1).

The baseline takes O(n) time and O(n+h) auxiliary list/call storage. An augmented balanced search tree with maintained subtree sizes can answer rank queries in O(log n), but needs update metadata not present here.

Exact-state walkthroughs

Reveal normal and boundary traces

Consume rank only on inorder emission

Input: {"tree":[3,1,4,null,2],"k":2} · Kth value / thrown outcome: 2

Step 1 of 8: Start an inorder rank query on a prevalidated BST.

The BST property is a precondition, not checked by this traversal. Stack top is at the right; only emissions consume rank.

Kth smallest — suspended ancestors and emitted ranks

Phase: initial. Current identity: T0.

Original objects — unchanged source edges

T0: 3left → T1right → T2
T1: 1left → nullright → T3
T2: 4left → nullright → null
T3: 2left → nullright → null

Requested one-based k: 2. Remaining rank: 2.

Suspended ancestors — stack top at right

Empty.

Emitted identities in increasing BST order

Empty.

Descending left consumes no rank. Only an emission decrements remaining; a matching emission returns before exploring its right subtree. Ordering is a BST precondition.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":"T3"},{"id":"T2","value":4,"left":null,"right":null},{"id":"T3","value":2,"left":null,"right":null}]`
root	`"T0"`
k	`2`
current	`"T0"`
stack	`[]`
remaining	`2`
emitted	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static int kthSmallest(Node root, int k) {
 9         if (k <= 0) throw new IllegalArgumentException("k must be positive");
10         ArrayDeque<Node> stack = new ArrayDeque<>();
11         Node current = root;
12         int remaining = k;
13         while (current != null || !stack.isEmpty()) {
14             while (current != null) { stack.push(current); current = current.left; }
15             Node node = stack.pop();
16             if (--remaining == 0) return node.value;
17             current = node.right;
18         }
19         throw new IllegalArgumentException("k exceeds node count");
20     }
21     private static void inorder(Node node, List<Integer> values) {
22         if (node == null) return;
23         inorder(node.left,values); values.add(node.value); inorder(node.right,values);
24     }
25     public static int baseline(Node root, int k) {
26         if (k <= 0) throw new IllegalArgumentException("k must be positive");
27         List<Integer> values = new ArrayList<>(); inorder(root,values);
28         if (k > values.size()) throw new IllegalArgumentException("k exceeds node count");
29         return values.get(k-1);
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start an inorder rank query on a prevalidated BST.
The BST property is a precondition, not checked by this traversal. Stack top is at the right; only emissions consume rank.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":"T3"},{"id":"T2","value":4,"left":null,"right":null},{"id":"T3","value":2,"left":null,"right":null}]
root
"T0"
k
2
current
"T0"
stack
[]
remaining
2
emitted
[]
phase
"initial"
Suspend an ancestor and descend its left edge.
Pending ancestors have not yet been emitted; stack size is not the sorted rank count.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":"T3"},{"id":"T2","value":4,"left":null,"right":null},{"id":"T3","value":2,"left":null,"right":null}]
root
"T0"
k
2
current
"T1"
stack
["T0"]
remaining
2
emitted
[]
phase
"descend"
Suspend an ancestor and descend its left edge.
Pending ancestors have not yet been emitted; stack size is not the sorted rank count.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":"T3"},{"id":"T2","value":4,"left":null,"right":null},{"id":"T3","value":2,"left":null,"right":null}]
root
"T0"
k
2
current
null
stack
["T0","T1"]
remaining
2
emitted
[]
phase
"descend"
Emit the next increasing value and consume one rank.
After r emissions, remaining=k−r. A zero remaining count returns before exploring the selected node’s right subtree.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":"T3"},{"id":"T2","value":4,"left":null,"right":null},{"id":"T3","value":2,"left":null,"right":null}]
root
"T0"
k
2
current
null
stack
["T0"]
remaining
1
emitted
[{"id":"T1","value":1}]
phase
"emit"
visited
"T1"
Continue with the emitted node’s right subtree.
The next left-spine descent exposes the smallest remaining value.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":"T3"},{"id":"T2","value":4,"left":null,"right":null},{"id":"T3","value":2,"left":null,"right":null}]
root
"T0"
k
2
current
"T3"
stack
["T0"]
remaining
1
emitted
[{"id":"T1","value":1}]
phase
"right"
visited
"T1"
Suspend an ancestor and descend its left edge.
Pending ancestors have not yet been emitted; stack size is not the sorted rank count.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":"T3"},{"id":"T2","value":4,"left":null,"right":null},{"id":"T3","value":2,"left":null,"right":null}]
root
"T0"
k
2
current
null
stack
["T0","T3"]
remaining
1
emitted
[{"id":"T1","value":1}]
phase
"descend"
Emit the next increasing value and consume one rank.
After r emissions, remaining=k−r. A zero remaining count returns before exploring the selected node’s right subtree.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":"T3"},{"id":"T2","value":4,"left":null,"right":null},{"id":"T3","value":2,"left":null,"right":null}]
root
"T0"
k
2
current
null
stack
["T0"]
remaining
0
emitted
[{"id":"T1","value":1},{"id":"T3","value":2}]
phase
"emit"
visited
"T3"
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
2

Empty tree has no first rank

Input: {"tree":[],"k":1} · Kth value / thrown outcome: "IllegalArgumentException"

Step 1 of 3: Start an inorder rank query on a prevalidated BST.

The BST property is a precondition, not checked by this traversal. Stack top is at the right; only emissions consume rank.

Kth smallest — suspended ancestors and emitted ranks

Phase: initial. Current identity: null.

Original objects — unchanged source edges

Empty tree.

Requested one-based k: 1. Remaining rank: 1.

Suspended ancestors — stack top at right

Empty.

Emitted identities in increasing BST order

Empty.

Descending left consumes no rank. Only an emission decrements remaining; a matching emission returns before exploring its right subtree. Ordering is a BST precondition.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[]`
root	`null`
k	`1`
current	`null`
stack	`[]`
remaining	`1`
emitted	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static int kthSmallest(Node root, int k) {
 9         if (k <= 0) throw new IllegalArgumentException("k must be positive");
10         ArrayDeque<Node> stack = new ArrayDeque<>();
11         Node current = root;
12         int remaining = k;
13         while (current != null || !stack.isEmpty()) {
14             while (current != null) { stack.push(current); current = current.left; }
15             Node node = stack.pop();
16             if (--remaining == 0) return node.value;
17             current = node.right;
18         }
19         throw new IllegalArgumentException("k exceeds node count");
20     }
21     private static void inorder(Node node, List<Integer> values) {
22         if (node == null) return;
23         inorder(node.left,values); values.add(node.value); inorder(node.right,values);
24     }
25     public static int baseline(Node root, int k) {
26         if (k <= 0) throw new IllegalArgumentException("k must be positive");
27         List<Integer> values = new ArrayList<>(); inorder(root,values);
28         if (k > values.size()) throw new IllegalArgumentException("k exceeds node count");
29         return values.get(k-1);
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start an inorder rank query on a prevalidated BST.
The BST property is a precondition, not checked by this traversal. Stack top is at the right; only emissions consume rank.
treeNodes
[]
root
null
k
1
current
null
stack
[]
remaining
1
emitted
[]
phase
"initial"
Traversal exhausted before the requested rank.
Every node was emitted, so this positive rank has no witness.
treeNodes
[]
root
null
k
1
current
null
stack
[]
remaining
1
emitted
[]
phase
"reject"
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
"IllegalArgumentException"

Largest valid rank at an int extreme

Input: {"tree":[0,-2147483648,2147483647],"k":3} · Kth value / thrown outcome: 2147483647

Step 1 of 10: Start an inorder rank query on a prevalidated BST.

The BST property is a precondition, not checked by this traversal. Stack top is at the right; only emissions consume rank.

Kth smallest — suspended ancestors and emitted ranks

Phase: initial. Current identity: T0.

Original objects — unchanged source edges

T0: 0left → T1right → T2
T1: -2147483648left → nullright → null
T2: 2147483647left → nullright → null

Requested one-based k: 3. Remaining rank: 3.

Suspended ancestors — stack top at right

Empty.

Emitted identities in increasing BST order

Empty.

Descending left consumes no rank. Only an emission decrements remaining; a matching emission returns before exploring its right subtree. Ordering is a BST precondition.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]`
root	`"T0"`
k	`3`
current	`"T0"`
stack	`[]`
remaining	`3`
emitted	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static int kthSmallest(Node root, int k) {
 9         if (k <= 0) throw new IllegalArgumentException("k must be positive");
10         ArrayDeque<Node> stack = new ArrayDeque<>();
11         Node current = root;
12         int remaining = k;
13         while (current != null || !stack.isEmpty()) {
14             while (current != null) { stack.push(current); current = current.left; }
15             Node node = stack.pop();
16             if (--remaining == 0) return node.value;
17             current = node.right;
18         }
19         throw new IllegalArgumentException("k exceeds node count");
20     }
21     private static void inorder(Node node, List<Integer> values) {
22         if (node == null) return;
23         inorder(node.left,values); values.add(node.value); inorder(node.right,values);
24     }
25     public static int baseline(Node root, int k) {
26         if (k <= 0) throw new IllegalArgumentException("k must be positive");
27         List<Integer> values = new ArrayList<>(); inorder(root,values);
28         if (k > values.size()) throw new IllegalArgumentException("k exceeds node count");
29         return values.get(k-1);
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start an inorder rank query on a prevalidated BST.
The BST property is a precondition, not checked by this traversal. Stack top is at the right; only emissions consume rank.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
"T0"
stack
[]
remaining
3
emitted
[]
phase
"initial"
Suspend an ancestor and descend its left edge.
Pending ancestors have not yet been emitted; stack size is not the sorted rank count.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
"T1"
stack
["T0"]
remaining
3
emitted
[]
phase
"descend"
Suspend an ancestor and descend its left edge.
Pending ancestors have not yet been emitted; stack size is not the sorted rank count.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
null
stack
["T0","T1"]
remaining
3
emitted
[]
phase
"descend"
Emit the next increasing value and consume one rank.
After r emissions, remaining=k−r. A zero remaining count returns before exploring the selected node’s right subtree.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
null
stack
["T0"]
remaining
2
emitted
[{"id":"T1","value":-2147483648}]
phase
"emit"
visited
"T1"
Continue with the emitted node’s right subtree.
The next left-spine descent exposes the smallest remaining value.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
null
stack
["T0"]
remaining
2
emitted
[{"id":"T1","value":-2147483648}]
phase
"right"
visited
"T1"
Emit the next increasing value and consume one rank.
After r emissions, remaining=k−r. A zero remaining count returns before exploring the selected node’s right subtree.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
null
stack
[]
remaining
1
emitted
[{"id":"T1","value":-2147483648},{"id":"T0","value":0}]
phase
"emit"
visited
"T0"
Continue with the emitted node’s right subtree.
The next left-spine descent exposes the smallest remaining value.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
"T2"
stack
[]
remaining
1
emitted
[{"id":"T1","value":-2147483648},{"id":"T0","value":0}]
phase
"right"
visited
"T0"
Suspend an ancestor and descend its left edge.
Pending ancestors have not yet been emitted; stack size is not the sorted rank count.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
null
stack
["T2"]
remaining
1
emitted
[{"id":"T1","value":-2147483648},{"id":"T0","value":0}]
phase
"descend"
Emit the next increasing value and consume one rank.
After r emissions, remaining=k−r. A zero remaining count returns before exploring the selected node’s right subtree.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":"T2"},{"id":"T1","value":-2147483648,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]
root
"T0"
k
3
current
null
stack
[]
remaining
0
emitted
[{"id":"T1","value":-2147483648},{"id":"T0","value":0},{"id":"T2","value":2147483647}]
phase
"emit"
visited
"T2"
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
2147483647

Reject zero before touching the tree

Input: {"tree":[1],"k":0} · Kth value / thrown outcome: "IllegalArgumentException"

Step 1 of 2: Start an inorder rank query on a prevalidated BST.

The BST property is a precondition, not checked by this traversal. Stack top is at the right; only emissions consume rank.

Kth smallest — suspended ancestors and emitted ranks

Phase: reject. Current identity: T0.

Original objects — unchanged source edges

T0: 1left → nullright → null

Requested one-based k: 0. Remaining rank: 0.

Suspended ancestors — stack top at right

Empty.

Emitted identities in increasing BST order

Empty.

Descending left consumes no rank. Only an emission decrements remaining; a matching emission returns before exploring its right subtree. Ordering is a BST precondition.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":1,"left":null,"right":null}]`
root	`"T0"`
k	`0`
current	`"T0"`
stack	`[]`
remaining	`0`
emitted	`[]`
phase	`"reject"`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static int kthSmallest(Node root, int k) {
 9         if (k <= 0) throw new IllegalArgumentException("k must be positive");
10         ArrayDeque<Node> stack = new ArrayDeque<>();
11         Node current = root;
12         int remaining = k;
13         while (current != null || !stack.isEmpty()) {
14             while (current != null) { stack.push(current); current = current.left; }
15             Node node = stack.pop();
16             if (--remaining == 0) return node.value;
17             current = node.right;
18         }
19         throw new IllegalArgumentException("k exceeds node count");
20     }
21     private static void inorder(Node node, List<Integer> values) {
22         if (node == null) return;
23         inorder(node.left,values); values.add(node.value); inorder(node.right,values);
24     }
25     public static int baseline(Node root, int k) {
26         if (k <= 0) throw new IllegalArgumentException("k must be positive");
27         List<Integer> values = new ArrayList<>(); inorder(root,values);
28         if (k > values.size()) throw new IllegalArgumentException("k exceeds node count");
29         return values.get(k-1);
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start an inorder rank query on a prevalidated BST.
The BST property is a precondition, not checked by this traversal. Stack top is at the right; only emissions consume rank.
treeNodes
[{"id":"T0","value":1,"left":null,"right":null}]
root
"T0"
k
0
current
"T0"
stack
[]
remaining
0
emitted
[]
phase
"reject"
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
"IllegalArgumentException"

Test the contract

Input: k=0 or negative
Output: IllegalArgumentException
Rejected before traversal.
Input: null, k=1
Output: IllegalArgumentException
No kth node.
Input: k=nodeCount
Output: largest BST value
Last valid rank.
Input: 100,000-node ordered chain
Output: first and last ranks correct
No recursive stack dependence.

Common mistakes and counterexamples

Use a general binary tree without checking the contract

Counterexample: Inorder of a non-BST need not be sorted.

Treat strict BST ordering as a precondition or explicitly pay for validation.

Subtract k on every descent

Counterexample: Pushing an ancestor is not emitting its value.

Consume rank only after popping the next inorder node.

Return a sentinel for invalid k

Counterexample: MIN or -1 can be valid answers.

Throw the specified exception on nonpositive or exhausted ranks.

Follow-ups

Support frequent rank queries under updates.

Store subtree sizes in a balanced BST and update them during rotations/insertion/deletion. One-off traversal does not provide that maintained index.

Return the kth node identity.

Return the popped Node instead of its value. The rank proof is unchanged, but tests should compare exact references.

Find rank in a BST with duplicates.

Specify whether occurrences or distinct values count and which side owns duplicates. Subtree size and ordering rules must use the same policy.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.