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

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	K^th 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).

Visualization Player

Solution❯

To find the kth largest element in a BST, we can use the property that an in-order traversal gives nodes in ascending order. So, by performing a reverse in-order traversal (right → node → left), we can access nodes in descending order. This allows us to find the kth largest node without needing to store all elements.

Case 1: Normal Case

In a typical BST with multiple nodes, we perform a reverse in-order traversal. At each node visited, we increment a counter. Once the counter equals k, we record that node’s value as the answer. For example, in a BST like [5,3,6,2,4,null,null,1], if k=3, we visit nodes in the order [6,5,4,…] and stop at the 3rd visited node, which is 4.

Case 2: k = 1 (Largest Element)

When k = 1, we're looking for the largest element in the BST. The traversal begins from the rightmost node, which will be the largest due to BST properties. So, the answer is simply the value of the rightmost node.

Case 3: Small BST

In small trees like [2,1,3], reverse traversal gives us [3,2,1]. The kth largest can be identified quickly by counting the nodes visited. For k = 2, we pick 2 as the result.

Case 4: Single Node Tree

If the BST has only one node, such as [5], the only possible valid value for k is 1. In this case, the answer is the node itself, i.e., 5.

Case 5: Empty Tree

If the BST is empty (no nodes), then there are no elements to choose from. Any value of k would be invalid in this context, and we should return an error message or handle this case explicitly in code to avoid runtime errors.

Algorithm Steps❯

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

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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


def kthLargest(root, k):
    count = 0
    result = None

    def traverse(node):
        nonlocal count, result
        if not node or result is not None:
            return
        traverse(node.right)
        count += 1
        if count == k:
            result = node.val
            return
        traverse(node.left)

    traverse(root)
    return result

# Example usage:
if __name__ == '__main__':
    # Construct a sample BST:
    #         5
    #        / \
    #       3   7
    #      / \   \
    #     2   4   8
    root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(7, None, TreeNode(8)))
    k = 2
    print(kthLargest(root, k))

⬅ Previous TopicMerge Two Binary Search Trees

Next Topic ⮕Find the kth Smallest Element in a Binary Search Tree

Comments

Loading comments...