Find the kth Largest Element in a Binary Search Tree - Algorithm, Visualization, Examples

Binary Search Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

You are given a Binary Search Tree (BST) and an integer k. Your task is to find the kth largest element in the BST. In a BST, the left subtree of a node contains nodes with values less than the node’s value, and the right subtree contains nodes with values greater than the node’s value.

The tree will contain unique values, and k is guaranteed to be a positive integer no greater than the number of nodes in the tree.

Examples❯

Input Tree (Level Order) k Kth Largest Description
[5, 3, 7, 2, 4, 6, 8]
3 6 In descending order [8, 7, 6, 5, 4, 3, 2], the 3rd largest is 6.
[20, 10, 30, 5, 15, 25, 35]
1 35 Largest element in the BST is 35 (rightmost leaf).
[15, 10, 20, null, 12, 17, 25]
5 12 Descending order is [25, 20, 17, 15, 12, 10]; 5th largest is 12.
[50, 30, 70, 20, 40, 60, 80]
7 20 In descending order [80, 70, 60, 50, 40, 30, 20]; 7th largest is 20.
[10]
1 10 Single node is both the largest and smallest, so 1st largest is 10.
[] 1 null Empty tree has no nodes, so kth largest is undefined (null).

Solution❯

Understanding the Problem

We are given a Binary Search Tree (BST), and we need to find the kth largest element in it. A BST has the property that for any given node, the left subtree contains values less than the node, and the right subtree contains values greater than the node.

To solve this, we can utilize reverse in-order traversal (right → node → left), which visits nodes in descending order. This approach allows us to find the kth largest element efficiently by counting how many nodes we’ve visited so far during the traversal.

Step-by-Step Solution with Example

Step 1: Choose an Example

Let’s consider the example BST: [5,3,6,2,4,null,null,1].

This represents the following BST structure:


        5
       /       3   6
     /     2   4
   /
  1

We are asked to find the k = 3rd largest element.

Step 2: Understand Reverse In-Order Traversal

In normal in-order traversal (Left → Node → Right), we get sorted ascending order. But here, we use reverse in-order (Right → Node → Left) to get descending order. As we visit each node, we keep a count.

Step 3: Traverse and Count

Start from the rightmost node (which is the largest):

  1. Visit 6 → count = 1
  2. Backtrack to 5 → count = 2
  3. Go to left child 3, then right child 4 → count = 3

Since count = 3 at node 4, we return 4 as the answer.

Step 4: Code Outline

We define a helper function to do reverse in-order traversal recursively, while maintaining a counter and storing the result once we reach the kth element.


// Java-style pseudocode
int count = 0;
int result = -1;

void reverseInorder(TreeNode 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);
}

Edge Cases

Case 1: k = 1 (Largest Element)

When k = 1, we want the largest element. Since the rightmost node in a BST is the largest, we can directly return the value of the rightmost node if we reach it first during traversal.

Case 2: Small BST

For a small BST like [2,1,3], reverse traversal visits nodes in the order [3,2,1]. If k = 2, the answer is 2.

Case 3: Single Node Tree

If the tree has just one node, say [5], then the only valid k is 1. The 1st largest element is the node itself: 5.

Case 4: Empty Tree

If the tree is empty, there are no elements to return. Any k in this scenario is invalid, and we must return an error or handle it gracefully (e.g., return -1 or throw an exception).

Case 5: k Greater Than Number of Nodes

If k is larger than the total number of nodes, the traversal will finish without finding the kth largest. We should check node count beforehand or handle this as an invalid input.

Finally

This problem teaches us how to apply a traversal technique that respects the properties of BSTs to solve problems efficiently. By understanding reverse in-order traversal and maintaining a count, we can find the kth largest element in O(H + k) time, where H is the height of the tree. Always remember to consider edge cases like empty trees, invalid k values, and small tree structures during implementation.

Algorithm Steps❯

  1. Given a binary search tree (BST) and an integer k.
  2. Perform a reverse in-order traversal (visit right subtree, then node, then left subtree) to process nodes in descending order.
  3. Maintain a counter of visited nodes.
  4. When the counter equals k, record the current node's value as the kth largest element and terminate the traversal.
  5. Return the recorded value.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void reverseInorder(TreeNode* root, int k, int* count, int* result) {
    if (!root) return;
    reverseInorder(root->right, k, count, result);
    (*count)++;
    if (*count == k) {
        *result = root->val;
        return;
    }
    reverseInorder(root->left, k, count, result);
}

int kthLargest(TreeNode* root, int k) {
    int count = 0, result = -1;
    reverseInorder(root, k, &count, &result);
    return result;
}

int main() {
    TreeNode* root = createNode(5);
    root->left = createNode(3);
    root->left->left = createNode(2);
    root->left->right = createNode(4);
    root->right = createNode(7);
    root->right->right = createNode(8);
    int k = 2;
    printf("%d\n", kthLargest(root, k));
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...