Kth Maximum Element in a Binary Search Tree

Finding the k-th maximum element in a Binary Search Tree reduces to one observation: reverse inorder traversal visits nodes in descending order, so counting visits and stopping at k gives the answer.

Why Reverse Inorder Traversal Works

A Binary Search Tree enforces a strict ordering rule at every node: all values in the left subtree are smaller, all values in the right subtree are larger. Standard inorder traversal (Left → Root → Right) exploits this to visit every node in ascending order. Reverse inorder traversal flips the direction to Right → Root → Left, which visits every node in descending order.

That descending sequence is precisely what the problem needs. If you walk the tree in descending order and count each node you visit, the node where the count first equals k is the k-th largest value in the tree. No sorting, no auxiliary array.

Compare the two traversal orders for a seven-node BST with values 5, 10, 15, 20, 25, 30, 35:

Traversal	Visit order
Inorder (L → N → R)	5 → 10 → 15 → 20 → 25 → 30 → 35
Reverse inorder (R → N → L)	35 → 30 → 25 → 20 → 15 → 10 → 5

For k = 3 the answer is 25 (third from the top of the descending sequence). Tree traversal variants are a standard topic in the BST section of technical rounds, and reverse inorder is the textbook method for rank-from-top queries.

Algorithm: Step-by-Step

The algorithm keeps a shared counter that increments each time a node is visited. When the counter matches k, the current node’s value is the answer.

• Step 1: Start at the root.
• Step 2: Recurse right (right subtree contains larger values).
• Step 3: Visit the current node. Increment the counter.
• Step 4: If counter == k, record the current node’s value and exit the traversal early.
• Step 5: Recurse left (left subtree contains smaller values).
• Step 6: If the traversal finishes without the counter reaching k, return -1 (k exceeds the tree size).

The early-exit at Step 4 is not optional. Without it, the algorithm degrades to a full O(n) traversal every time, discarding the efficiency of the BST ordering property.

Worked Example: 7-Node BST

Consider the following BST:

        20
       /  \
     10    30
    / \   / \
   5  15  25  35

Nodes in descending order (reverse inorder): 35, 30, 25, 20, 15, 10, 5.

Trace for k = 3 (count starts at 0):

• Visit right subtree of 20, then right subtree of 30, arriving at 35.
• Visit 35: count becomes 1. k = 3, no match. Move to left subtree of 35 (empty).
• Back at 30: count becomes 2. k = 3, no match. Visit left subtree of 30.
• Arrive at 25. Visit 25: count becomes 3. k = 3, match. Return 25.

Result for k = 3: 25

Other k values on the same tree:

• k = 1: stops immediately at 35 (overall maximum).
• k = 7: visits all seven nodes, returns 5 (the minimum value equals the 7th maximum of 7 nodes).
• k = 8: visits all seven nodes, counter reaches 7 but never 8, returns -1.

This tree has height H = 2 (three levels, root at level 0). The k = 3 traversal visited 4 nodes before early-exit: three nodes on the right path plus 25 itself, which is H + k = 2 + 3 = 5 in the worst walk, 4 in the actual trace. The O(H + k) bound holds.

For a related pattern where you track a running counter through a linear scan, see the equilibrium index problem.

Code Implementation

C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

class BST {
    int count = 0;
    int result = -1;

    void reverseInorder(Node* node, int k) {
        if (node == nullptr || count >= k) return;
        reverseInorder(node->right, k);   // go right first
        ++count;
        if (count == k) {
            result = node->val;
            return;
        }
        reverseInorder(node->left, k);    // go left last
    }

public:
    int kthMaximum(Node* root, int k) {
        count = 0;
        result = -1;
        reverseInorder(root, k);
        return result;  // -1 if k > tree size
    }
};

int main() {
    //   Build the 7-node example tree
    Node* root = new Node(20);
    root->left  = new Node(10); root->right = new Node(30);
    root->left->left  = new Node(5);  root->left->right  = new Node(15);
    root->right->left = new Node(25); root->right->right = new Node(35);

    BST bst;
    cout << "k=1: " << bst.kthMaximum(root, 1) << "\n";  // 35
    cout << "k=3: " << bst.kthMaximum(root, 3) << "\n";  // 25
    cout << "k=7: " << bst.kthMaximum(root, 7) << "\n";  // 5
    cout << "k=8: " << bst.kthMaximum(root, 8) << "\n";  // -1
    return 0;
}

Output:

k=1: 35
k=3: 25
k=7: 5
k=8: -1

Java

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; }
}

class KthMaxBST {
    private int count = 0;
    private int result = -1;

    private void reverseInorder(Node node, int k) {
        if (node == null || count >= k) return;
        reverseInorder(node.right, k);
        ++count;
        if (count == k) {
            result = node.val;
            return;
        }
        reverseInorder(node.left, k);
    }

    public int kthMaximum(Node root, int k) {
        count = 0;
        result = -1;
        reverseInorder(root, k);
        return result;
    }

    public static void main(String[] args) {
        Node root = new Node(20);
        root.left  = new Node(10); root.right = new Node(30);
        root.left.left  = new Node(5);  root.left.right  = new Node(15);
        root.right.left = new Node(25); root.right.right = new Node(35);

        KthMaxBST solver = new KthMaxBST();
        System.out.println("k=1: " + solver.kthMaximum(root, 1));  // 35
        System.out.println("k=3: " + solver.kthMaximum(root, 3));  // 25
        System.out.println("k=7: " + solver.kthMaximum(root, 7));  // 5
        System.out.println("k=8: " + solver.kthMaximum(root, 8));  // -1
    }
}

Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def kth_maximum(root, k):
    """Return the k-th maximum value in the BST, or -1 if k > tree size."""
    count = [0]
    result = [-1]

    def reverse_inorder(node):
        if node is None or count[0] >= k:
            return
        reverse_inorder(node.right)   # go right first
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        reverse_inorder(node.left)    # go left last

    reverse_inorder(root)
    return result[0]

# Build the 7-node example tree
root = Node(20)
root.left  = Node(10); root.right = Node(30)
root.left.left  = Node(5);  root.left.right  = Node(15)
root.right.left = Node(25); root.right.right = Node(35)

print(kth_maximum(root, 1))   # 35
print(kth_maximum(root, 3))   # 25
print(kth_maximum(root, 7))   # 5
print(kth_maximum(root, 8))   # -1

Output matches the worked example exactly. Verify this against any compiler before submitting in an interview.

Complexity Analysis

Time complexity: O(H + k)

The algorithm descends the right spine to reach the largest node in O(H) steps, then visits up to k nodes on the way back. Total node visits: at most H + k. For more on deriving these bounds from structure, see the space complexity of algorithms guide.

Two concrete cases:

• Balanced BST (complete or nearly complete): height H = O(log n). Total time: O(log n + k).
• Skewed BST (all nodes in the right subtree, like a linked list): height H = n. Total time: O(n + k) = O(n) for k much smaller than n.

The WP article for this topic cited O(n + k) as the time complexity. That figure describes only the worst-case skewed tree. The tighter bound O(H + k) applies to all BSTs and is the answer a product-company interviewer expects.

Space complexity: O(H)

Every recursive call adds one frame to the call stack. The maximum recursion depth equals the tree height H, giving O(log n) for a balanced BST and O(n) for a skewed one.

Edge Cases

Four cases worth coding explicitly before any interview or online judge submission:

• k = 1: the algorithm stops at the first node visited (the rightmost node), returning the overall maximum. No traversal of the left subtree occurs.
• k = total nodes: the algorithm visits every node in the tree, returning the minimum value (the leftmost node). Functionally correct but uses the full O(H + k) = O(n) budget.
• k = 0 or negative: invalid input. Return -1 or throw an IllegalArgumentException before entering the traversal. Guard this at the entry point, not inside the recursive function.
• Empty tree (root is null): the base case returns immediately, result stays -1. Correct behaviour without special-casing.

For another problem where a boundary case flips the whole answer, see finding all symmetric pairs in an array.

O(1) Space: Morris Traversal

The recursive and iterative approaches above both use O(H) auxiliary space for the call stack or explicit stack. If the problem explicitly requires O(1) extra space (some online judges enforce a tight memory limit), Morris traversal provides an alternative.

Morris in-order traversal threads the tree’s null right pointers temporarily so that a node can be visited, then reached again, without a stack. Applied in reverse (right-first threading), it produces the same descending visit order as reverse inorder but with O(1) auxiliary space.

The trade-off: the algorithm temporarily modifies the tree during traversal, which is a problem in concurrent or read-only settings. It also carries a higher constant factor than the recursive version. For placement interviews, the recursive approach is the expected answer; Morris traversal is the follow-up for “can you do it in O(1) space?”

---

The O(H + k) bound on this problem is the kind of complexity reasoning product-company technical screens ask you to articulate, not just reach the right answer. Once the BST layer of your prep is solid, the next skill tier most placement-focused students build is applied AI engineering. TinkerLLM is that next layer at ₹299, a practical entry point before committing to a longer programme.