Find Kth Largest Value In BST

Tags

Find Kth Largest Value In BST

Category

Binary Search Trees (BST)

Difficulty

Medium

Problem Statement

Given a Binary Search Tree (BST) and a positive integer k, find the kth largest value contained in the BST. You may assume that k is less than or equal to the number of nodes in the tree.

Intuition

In a BST, an in-order traversal visits nodes in ascending order. By performing a reverse in-order traversal (right subtree first, then current node, then left subtree), we visit nodes in descending order. The kth node visited in this reverse traversal is the kth largest value. We can stop early once we have found the kth node, avoiding unnecessary work.

Approach

  1. Initialize a counter to track how many nodes have been visited and a variable to store the result.
  2. Perform a reverse in-order traversal starting from the root: a. Recursively visit the right subtree. b. Increment the counter. If the counter equals k, record the current node's value and return. c. Recursively visit the left subtree.
  3. Return the recorded value.

Pseudocode

function findKthLargest(tree, k):
    info = { count: 0, result: -1 }
    reverseInOrder(tree, k, info)
    return info.result

function reverseInOrder(node, k, info):
    if node is null or info.count >= k:
        return
    reverseInOrder(node.right, k, info)
    if info.count < k:
        info.count += 1
        if info.count == k:
            info.result = node.value
            return
        reverseInOrder(node.left, k, info)

Time & Space Complexity

  • Time: O(h + k), where h is the height of the tree. We descend to the rightmost node (O(h)) then visit k nodes. In the worst case (k = n), this is O(n).
  • Space: O(h) for the recursion call stack, where h is the height. For a balanced BST, h = O(log n). For a skewed tree, h = O(n).

Key Insights

  • Reverse in-order traversal is the key technique: it converts the "kth largest" problem into "visit the kth node."
  • Early termination once the kth node is found avoids traversing the entire tree.
  • This approach requires no extra data structure beyond the call stack.
  • An alternative approach is to do a full in-order traversal, collect all values in an array, and return array[n - k], but this uses O(n) extra space and always visits all nodes.

Edge Cases

  • k = 1: return the largest value (the rightmost node in the BST).
  • k = n (total number of nodes): return the smallest value (the leftmost node).
  • Single-node tree with k = 1: return that node's value.
  • Skewed tree (all left children or all right children): traversal still works correctly, but the recursion depth is O(n).

Linked mentions