Problem statement

Given the root of a binary search tree with distinct values and an integer k, return the k-th largest value in the tree (k = 1 is the maximum).

Example 1

Input: root = [4,2,9], k = 2
Output: 4
Explanation: In decreasing order the values are 9, 4, 2; the second is 4.

Example 2

Input: root = [9,null,10], k = 1
Output: 10
Explanation: The largest value is 10.

Example 3

Input: root = [50,30,70,20,40,60,80], k = 3
Output: 60
Explanation: 80, 70, 60, … — the third largest is 60.

Constraints

• 1 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^5
• all node values are distinct
• 1 <= k <= number of nodes

Hints for Kth Largest Element in BST

1. Hint 1

   An in-order traversal of a search tree lists the values in increasing order. Which traversal lists them in decreasing order?

2. Hint 2

   Reverse in-order: right subtree, node, left subtree.

3. Hint 3

   Count the nodes as the reverse in-order traversal emits them and stop at the k-th — no need to visit the rest.

How to solve Kth Largest Element in BST

Reverse in-order traversal (right, node, left) visits a search tree's values from largest to smallest, so the k-th node it visits is the answer.

Approach

1. Start at the root with an empty stack.
2. Push nodes while moving right, down to the largest unvisited node.
3. Pop a node: it is the next value in decreasing order. Decrement k; when k reaches 0, return its value.
4. Otherwise continue from the popped node's left child.

Why it works

For any node, every value in its right subtree is larger and every value in its left subtree is smaller, so visiting right, then the node, then left emits a strictly decreasing sequence; its k-th element is the k-th largest value.

Complexity

• Time — O(h + k)
• Space — O(h) for the stack

Pitfalls

• Collecting all values and sorting is O(n log n) and ignores the ordering already in the tree.
• k counts from the largest: k = 1 is the maximum, not the minimum.

Reference solution

Python

from typing import Optional

def kthLargest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.right
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.left
    return -1

Java

public static int kthLargest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) { stack.push(node); node = node.right; }
        node = stack.pop();
        if (--k == 0) return node.val;
        node = node.left;
    }
    return -1;
}

C++

int kthLargest(TreeNode* root, int k) {
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (!stack.empty() || node) {
        while (node) { stack.push_back(node); node = node->right; }
        node = stack.back();
        stack.pop_back();
        if (--k == 0) return node->val;
        node = node->left;
    }
    return -1;
}

JavaScript

var kthLargest = function(root, k) {
    var stack = [], node = root;
    while (stack.length > 0 || node !== null) {
        while (node !== null) { stack.push(node); node = node.right; }
        node = stack.pop();
        if (--k === 0) return node.val;
        node = node.left;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Ceil in BST Easy
• Nodes at Distance K from Root Easy