432. Find the Kth Largest Element in a BST

Given a binary search tree and a value k, print the kth largest value in the tree (1-indexed). The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). k is given on the next line.

Input: First line contains space-separated level-order tokens describing the BST ('N' marks an absent child). Second line contains the integer k. Output: Print a single integer - the kth largest value in the BST.

1 <= k <= number of nodes <= 10^5

Recognizing that 'kth largest via reverse-inorder' and 'kth smallest via inorder' are the exact same technique mirrored is a good example of not treating superficially different-sounding problems as requiring entirely separate solutions.

Find the kth largest value stored in a binary search tree. Brute force: Perform a normal inorder traversal, collect ALL values ascending, then index into position (n - k), where n is the total node count - this works but requires knowing n upfront and doesn't stop early. Optimised: A REVERSE-inorder traversal directly visits values in descending order, so the kth value visited IS the kth largest with no extra index arithmetic needed - stopping the traversal early the moment the counter reaches k avoids visiting the rest of the tree unnecessarily.

Augment every node with the size of its own subtree, then answer a query with a single guided walk from the root instead of any full traversal: at each node, if its right subtree's size is >= k, recurse right; if the right subtree's size is exactly k-1, the current node is the answer; otherwise subtract (right-subtree size + 1) from k and recurse left. Because each step is decided in O(1) using the stored sizes rather than by visiting every node in between, this is the standard order-statistics-tree technique, and it especially pays off when the tree supports many such queries or updates rather than just one. Time: O(H) per query after O(n) size preprocessing Space: O(n)

Perform a standard in-order traversal of the BST (left, node, right), which visits every node's value in strictly ascending order, storing all n values into a list as you go. Once the traversal finishes, the kth largest value is simply the element at index n-k (0-indexed) of that sorted list. Time: O(n) Space: O(n)

Perform a reverse in-order traversal instead (right subtree, node, left subtree), which visits every node's value in descending order; keep a running counter that increments on each visit, and as soon as it reaches k, that node's value is the answer and the traversal stops immediately without storing anything or continuing to visit the rest of the tree. This avoids building any auxiliary list, needing only the recursion stack, and can finish well before touching all n nodes when k is small. Time: O(H + k) Space: O(H)

1. Perform a REVERSE-INORDER traversal (right subtree, node, left subtree) - for a BST, this visits every value in strictly DESCENDING order. 2. Keep a counter, incrementing it each time you visit a node. 3. The moment the counter reaches k, that node's value is your answer.

Time: O(h + k) in the best implementations - proportional to reaching the largest value plus however many nodes are visited before the counter reaches k. Space: O(h) for the recursion stack.

Test with k=1 (the maximum value), k equal to the total node count (the minimum value), a single-node tree, and a tree with 10^5 nodes for performance.

Be ready to point out this is simply the mirror image of 'kth smallest' - swapping the traversal direction (right-node-left instead of left-node-right) is the only change needed, a nice small insight to state confidently.