Find the kth Maximum Value in a BST

Given the root of a binary search tree and a number k, return the kth largest value (k = 1 is the maximum). Return an empty OptionalInt if the tree has fewer than k nodes.

Example

Text

Values inserted: 6, 4, 9, 2, 5, 8, 12, 10, 14
k = 1 -> 14,   k = 3 -> 10,   k = 10 -> empty

graph TB
    a["6"] --> b["4"]
    a --> c["9"]
    b --> d["2"]
    b --> e["5"]
    c --> f["8"]
    c --> g["12"]
    g --> h["10"]
    g --> i["14"]

In decreasing order the values are 14, 12, 10, 9, 8, 6, 5, 4, 2, so the 3rd largest is 10.

Brute force: collect the sorted values

An in-order traversal (left, node, right) of a BST visits the values in ascending order. Collect them into an ArrayList. The kth largest is at index size - k.

A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root. The fields are mutable, so no wrapper type is needed. OptionalInt is a container that holds either one int or nothing.

Java

import java.util.ArrayList;
import java.util.List;
import java.util.OptionalInt;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static void inOrder(TreeNode root, List<Integer> out) {
        if (root == null) return;
        inOrder(root.left, out);
        out.add(root.val);
        inOrder(root.right, out);
    }

    static OptionalInt kthMax(TreeNode root, int k) {
        List<Integer> sorted = new ArrayList<>();
        inOrder(root, sorted);
        if (k < 1 || k > sorted.size()) return OptionalInt.empty(); // k == 0 or k > size
        return OptionalInt.of(sorted.get(sorted.size() - k));
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 8, 12, 10, 14);
        System.out.println(kthMax(root, 1) + " " + kthMax(root, 3) + " " + kthMax(root, 10));
    }
}

Output

OptionalInt[14] OptionalInt[10] OptionalInt.empty

Time: O(n). Space: O(n) for the list of values.

Optimal: reverse in-order, stopping at k

Visit the nodes in right, node, left order instead. That produces the values from largest to smallest, so you can stop after the kth visit. An explicit stack makes stopping easy (a recursive version would need to pass the counter and the result back up through every call).

The loop is the standard iterative in-order traversal with left and right swapped:

From the current node, go right as far as possible, pushing each node onto the stack.
Pop a node and visit it. This is the next-largest value.
Move to its left child and repeat.

ArrayDeque used with push and pop is the standard stack in Java.

Walkthrough with k = 3:

step	pushed while going right	popped (visit)	count
1	6, 9, 12, 14	14	1
2	(14 has no left child)	12	2
3	10 (12's left child)	10	3 → return 10

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.OptionalInt;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static OptionalInt kthMax(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        int seen = 0;
        while (true) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.right;
            }
            if (stack.isEmpty()) return OptionalInt.empty(); // fewer than k nodes
            TreeNode node = stack.pop();
            seen++;
            if (seen == k) return OptionalInt.of(node.val);
            cur = node.left;
        }
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 8, 12, 10, 14);
        System.out.println(kthMax(root, 1) + " " + kthMax(root, 3) + " " + kthMax(root, 10));
        System.out.println(kthMax(root, 9));
        System.out.println(kthMax(root, 0) + " " + kthMax(null, 1));
    }
}

Output

OptionalInt[14] OptionalInt[10] OptionalInt.empty
OptionalInt[2]
OptionalInt.empty OptionalInt.empty

Time: O(h + k): reaching the maximum takes h steps, and each of the next k visits costs amortized O(1). Space: O(h) for the stack.

For the kth smallest (LeetCode 230), use the normal in-order direction: go left first, then right.

Edge cases

k = 0: no 0th largest exists. The brute force returns an empty result from its range check. The stack version never reaches seen == 0, so it runs to the end and returns an empty result.
k larger than the tree: empty.
Duplicate values: each copy counts as a separate position.