Start practising

Kth Largest Element in BST

Easy Trees & BST Reverse Inorder Traversal

Kth Largest Element in BST is a easy trees & bst problem solved with the reverse inorder traversal pattern. The best approach, optimal (reverse inorder, stop early), runs in O(h + k) time and O(h) space. Below are 2 approaches in Java, from inorder, then index from the end up.

Problem

Given the root of a BST and an integer k, return the k-th largest value. This is the mirror of Kth Smallest and teaches reverse inorder traversal.

Examples

Example 1

Input
root = [4, 2, 9], k = 2
Output
4
Why
Descending: 9, 4, 2.

Example 2

Input
root = [9, null, 10], k = 1
Output
10

Constraints

  • 1 <= k <= n <= 10^5; unique values.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Inorder, then index from the endO(n)O(n)
Optimal (reverse inorder, stop early)O(h + k)O(h)

1Inorder, then index from the end

TimeO(n)
SpaceO(n)

Collect the sorted inorder list and return element n - k.

  1. list = inorder(root); return list.get(n - k).
Java
class Solution {
    public int kthLargest(TreeNode root, int k) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        return vals.get(vals.size() - k);
    }

    private void inorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out);
        out.add(n.val);
        inorder(n.right, out);
    }
}

2Optimal (reverse inorder, stop early)

TimeO(h + k)
SpaceO(h)

Traverse right subtree, node, left subtree, which visits values in descending order. Count visits and stop at the k-th.

  1. Push the right spine; pop; if --k == 0 return val; go left.
Java
class Solution {
    public int kthLargest(TreeNode root, int k) {
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root;
        while (true) {
            while (cur != null) { st.push(cur); cur = cur.right; }
            cur = st.pop();
            if (--k == 0) return cur.val;
            cur = cur.left;
        }
    }
}

Edge cases to test

  • k = 1 (the maximum)
  • k = n (the minimum)

Hints

Hint 1

Reverse inorder (right, node, left) visits values from largest to smallest.

FAQ

What is the best time complexity for Kth Largest Element in BST?

Optimal (reverse inorder, stop early) runs in O(h + k) time and O(h) extra space.

Which pattern does Kth Largest Element in BST use?

It is a trees & bst problem that uses the reverse inorder traversal pattern. Other problems with the same pattern: Kth Smallest Element in a BST.

Is there a brute force solution for Kth Largest Element in BST?

Yes. Inorder, then index from the end takes O(n) time and O(n) space. Collect the sorted inorder list and return element n - k.

Which edge cases should I test for Kth Largest Element in BST?

k = 1 (the maximum); k = n (the minimum).