ProgramGuru.org

ProgramGuru.org

Find the kth Largest Element in a Binary Search Tree

Visualization

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.

Find the kth Largest Element in a Binary Search Tree - Code Examples Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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))